单点加区间查的线段树，每个线段树区间的值代表所维护序列在这个区间的总和；区间加单点查的线段树，每个线段树区间的值代表对这个区间总体加了多少。区间加区间查的线段树可以通过综合两种思想实现标记的永久化。
线段树将每一个修改或查询区间拆分为 \(O(\log w)\) 个线段树区间，只要保证每次操作只访问这些线段树区间和它们的祖先就能保证正确的复杂度。考虑每一个询问的线段树区间的答案由哪些修改区间贡献。情况1，如果一个修改完全被线段树区间包含或者部分交叉，那么处理这个修改的时候就会路过该节点，因此这个修改为该节点带来的贡献可以直接在该节点算清。情况2，如果一个修改完全包含了某线段树节点，处理修改的时候是不可能走到这个节点的，但我们可以在查询到这个节点的时候处理：记下从根到该节点的路径上所有这样的修改带来的贡献，与该节点自身已经算好的情况1的答案，加在一起就是所有情况的最终答案。因此每个节点需要存储一个累计值和一个标记，前者记录节点子树内的所有修改对该节点的贡献，后者记录在根到该节点路径上的所有修改对该节点整个子树的贡献。把贡献分成到根的路径和子树这样的两部分即可实现标记永久化。
标签：标记,线段,修改,永久化,区间,节点 From： https://www.cnblogs.com/nkxjlym/p/18353961