关于一棵线段树
  • 板块学术版
  • 楼主RNTBW
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/5/5 22:31
  • 上次更新2023/10/23 16:33:17
查看原帖
关于一棵线段树
643735
RNTBW楼主2023/5/5 22:31

如果我想实现:

  1. 区间修改,输入一个数 zz,将范围内大于 zz 的数修改为 zz

  2. 单点查询

我想了一下可以维护一个 cov 标记来记录这个区间范围内的值是否相等

查询时如果 cov=1 直接返回,否则就 pushdown 之后向下走

那么由于我太弱了,想了一下觉得问一下比较好qwq:

  1. 这样做的正确性是否保证?

  2. 那我的 update 是不是该这么写:

{
	if(x<=l&&r<=y)
    	{
        	....//其它操作
        	tree[p].cov=1;
            	return;
    	}
	tree[p].cov=0;
    	pushdown(p);
    	int mid=(l+r)>>1;
       	//pushup
}
  1. 这样做的时间复杂度是否在 O(nlog⁡2n)O(n\log_2n) 以内?
2023/5/5 22:31
加载中...