线段树哲学-个人总结
线段树哲学
写完线段树读一遍有没有漏掉pushup和pushdown
建树方法
为了加快时间,我采用堆的方法,即点
这样空间复杂度就是
对于build,我采用递归建树;每次查找时,将
对于pushup和pushdown
重要的哲学来了;
此哲学已变。
本人习惯:打上lazy标记表示,此区间内(包含此节点)的数据未更新
现在改了
正确时机:
修改时:
总结:直接返回要下放,查询子区间要下放,up前要将子区间的标记也下放
void update(int x, int l, int r, int ql, int qr, const Mat &k) {
if (ql <= l && r <= qr) {
lz[x] *= k; // 打上lazy标记
down(x);// 立即下放标记
return;
}
down(x);// 更新子区间前先下放标记
gm;
if (ql <= mid) update(ls, l, mid, ql, qr, k);
else down(ls);
if (mid < qr) update(rs, mid + 1, r, ql, qr, k);
else down(rs);
// 注意,因为之后要pushup,所以左右区间都要正确更新,即,每个区间如果不访问,要特地pushdown一下,这样pushup结果才能对;
up(x);
}
注意,对于标记互相冲突(有先后顺序的标记),应该在进入节点时先pushdown一遍;
求解时:
总结:每个区间先pushdown,不用pushup
Mat query(int x, int l, int r, int ql, int qr) {
down(x); // 先下放标记
if (ql <= l && r <= qr) {
return tre[x];
}
gm;
Mat ret;
if (ql <= mid) ret = query(ls, l, mid, ql, qr);
if (mid < qr) ret += query(rs, mid + 1, r, ql, qr);
// 查询子区间
return ret;
}
对于区间修改,是直接覆盖lazy标记
别瞎用else!!!
对于区间乘法和加法,在下放标记时,要对子区间的加法标记乘上父区间的乘法标记
整体二分线段树写挂祭
修改时,先下方标记,再递归!
分清N,M!
pushdown判断数组越界时,不要搞混数组大小!
如果选择的是无脑pushdown,务必不要下放叶节点
线段树优化常数
当询问完全在一个区间时,直接return,不要再合并1次;