动态开点线段树使用场景\(4\timesn\)开不下。值域需要平移（有负数）。什么时候开点显然，访问的节点不存在时（只会在修改递归时开点）。trick区间里面有负数时，\(mid=(l+R-1)/2\)。防止越界。例如区间\([-1,0]\)。开点上限考虑到update一次最多开\(\logV\)个点（最多递归\(\logV\)次）。所以总空间应当开\(O(m\logn)\)。代码#include#defineintlonglongusingnamespacestd;inttot;intn,q;constintmaxn=4e6+114;structNode{ intval,lt,rt,tag;

动态开点线段树使用场景\(4\timesn\)开不下。值域需要平移（有负数）。什么时候开点显然，访问的节点不存在时（只会在修改递归时开点）。trick区间里面有负数时，\(mid=(l+R-1)/2\)。防止越界。例如区间\([-1,0]\)。开点上限考虑到update一次最多开\(\logV\)个点（最多递归\(\logV\)次）。所以总空间应当开\(O(m\logn)\)。代码#include#defineintlonglongusingnamespacestd;inttot;intn,q;constintmaxn=4e6+114;structNode{ intval,lt,rt,tag;

使用场景维护的区间太大以至于\(4N\)存不下，通常是权值线段树；维护的区间下标存在负数；时间复杂度全部开点，则\(O(2N-1)\)每递归一次，最多开点\(O(\log_N)\)，若调用\(M\)次，\(O(M\log_N)\)原理若一段子区间[L,R]对应的线段树节点为cur，当不需要递归时，就不建点；当调用addtag()时，新建节点。注意事项没有build函数；addtag的节点cur要取址；有负数区间时，mid=(lt+rt-1)/2；根节点root为\(1\)代码#includeusingnamespacestd;#definelc(x)tree[x].lc#definerc(x)

使用场景维护的区间太大以至于\(4N\)存不下，通常是权值线段树；维护的区间下标存在负数；时间复杂度全部开点，则\(O(2N-1)\)每递归一次，最多开点\(O(\log_N)\)，若调用\(M\)次，\(O(M\log_N)\)原理若一段子区间[L,R]对应的线段树节点为cur，当不需要递归时，就不建点；当调用addtag()时，新建节点。注意事项没有build函数；addtag的节点cur要取址；有负数区间时，mid=(lt+rt-1)/2；根节点root为\(1\)代码#includeusingnamespacestd;#definelc(x)tree[x].lc#definerc(x)