【线段树】动态开点
使用场景[*]维护的区间太大以至于 \(4N\) 存不下，通常是权值线段树；
[*]维护的区间下标存在负数；
时间复杂度
[*]全部开点，则 \(O(2N - 1)\)
[*]每递归一次，最多开点 \(O(\log_N)\) ，若调用 \(M\) 次， \(O(M\log_N)\)
原理
[*]若一段子区间 对应的线段树节点为 cur ，当不需要递归时，就不建点；
[*]当调用 addtag() 时，新建节点。
注意事项
[*]没有 build 函数；
[*]addtag 的节点 cur 要取址；
[*]有负数区间时， mid = (lt + rt - 1) / 2；
[*]根节点 root 为 \(1\)
代码
#includeusing namespace std;#define lc(x) tree.lc#define rc(x) tree.rc#define sum(x) tree.val#define tag(x) tree.tagconst int N = 1e5 + 5;int n, m, tot;long long astruct node{ long long tag, val; int lc, rc;}tree;void addtag(int &cur, int lt, int rt, long long val) //注意取值符 { if(cur == 0) //结点不存在就新建立 cur = ++tot; sum(cur) += (rt - lt + 1) * val; tag(cur) += val; return ;}void pushup(int cur){ sum(cur) = sum(lc(cur)) + sum(rc(cur)); return ;}void pushdown(int cur, int lt, int rt){ if(lt >= rt) return ; int mid = (lt + rt - 1) / 2; addtag(lc(cur), lt, mid, tag(cur)); addtag(rc(cur), mid+1, rt, tag(cur)); tag(cur) = 0; return ;}void update(int cur, int lt, int rt, int qx, int qy, long long val){ if(qy < lt || qx > rt) //不归cur管 return ; if(qx > m; int root = 1; //根结点编号 tot = 1; //总结点数量 for(int i = 1; i > x; update(root, 1, n, i, i, x); } for(int i = 1; i > opt >> x >> y; if(opt == 1) { cin >> val; update(root, 1, n, x, y, val); //结点编号、管辖的左右边界、修改的左右边界、修改的值 } else cout > 1; return query(lc(cur), ql, qr, L, mid) + query(rc(cur), ql, qr, mid + 1, R); } signed main(){int ri, le; cin >> n >> le >> ri; int root = 1; tot = 1; for(int i = 1; i > x; res = res + x; }long long ans = 0;update(root, res, 1);for (int i = 1; i
页:
[1]