线段树易错处

\(updata:2021.12.1\) , 复习线段树.

\(① :\) \(build\)

void build(int l,int r){
	int sur = ++cnt;
	tree[sur].l = l , tree[sur].r = r;
	tree[sur].at = 0 , tree[sur].mt = 1;
	if(l != r){
		int mid = (l+r)>>1;
		tree[sur].ls = cnt+1; 
		build(l,mid);
		tree[sur].rs = cnt+1; 
		build(mid+1,r);
		int ls = tree[sur].ls , rs = tree[sur].rs;
		tree[sur].v = (tree[ls].v + tree[rs].v)% M;
	} 
	else tree[sur].v = a[l]%M;
}

\(① :\) 开头将 tree[sur].l = l , tree[sur].r = r; 弄好 , 防止将单个点 \(l,r\) 忘了.

\(② :\) tree[sur].ls = cnt+1 , 而不是 tree[sur].ls = ++cnt , 其实 \(cnt+1\) 是预判 , 下一步进行的 \(++cnt\) , 这时的 \(cnt\) 就等于 上一步的 \(cnt+1\) , 这样就能准确地找到左右儿子的编号 , 同时注意先确定编号 , 再递归.

\(③ :\) tree[sur].v = (tree[ls].v + tree[rs].v)% M; , 注意更新值.

\(② :\) \(Mul\) 与 \(Add\)

$①: $ 注意是 \(int mid = (tree[k].l + tree[k].r)>>1;\) , 而不是 \(int mid = (l + r)>>1;\) , 因为tree[k].l , tree[k].r 是作为大区间 , l,r是小区间 , 要以大区间 \(mid\) , 定位小区间的位置.

$②: $ 注意是 \(if(r<=mid)\) 等于号不能掉 , 这是因为初始化时 [l,mid] 就认为是左儿子的位置.

$③: $ 注意回溯时一定要更新父亲的值.

$③: $ \(lazytag\)

其实就是乘法加法运算法则的问题 , 乘法能影响之前的加法 , 而加法不能影响之前的乘法.( \(CF1542B\) )

注意在 \(pushdown\) 时乘法 \(tag\) 要变为 \(1\) , 加法 \(tag\) 要变为 \(0\).

但我现在都没搞懂为什么更新时要 \(pushdown\) , 我认为查询时 \(pushdown\) 就可以啦 , 然而这是错的.