线段树哲学-个人总结

# 线段树哲学 **写完线段树读一遍有没有漏掉pushup和pushdown** ## 建树方法 为了加快时间，我采用堆的方法，即点$x$的左儿子是$x<<1$ ，右儿子是$x<<1|1$，可能会牺牲一部分空间 **这样空间复杂度就是$O(kn)$，开数组的时候，最好开$N<<3$,最少开$N<<2$** 对于build，我采用递归建树；每次查找时，将$l,r$作为参数传入给函数 ## 对于pushup和pushdown 重要的哲学来了； *此哲学已变。* **本人习惯：打上lazy标记表示，此区间内（包含此节点）的数据未更新** ~~现在改了~~ ### 正确时机： 修改时： **总结：直接返回要下放，查询子区间要下放，up前要将子区间的标记也下放** ```cpp 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** ```cpp 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次； ## 线段树判定当$rs<M$成立时，这个点不一定是叶子！