动态开点线段树
引入
普通的线段树写法有一个显然的缺点——空间。堆式存贮使得我们开线段树时需要用 $ 4n $ 的空间。冗余空间高达 $ 2n $ 。而且，在大多数情况下线段树中并不是每个节点都会被用到，这时我们就可以使用动态开点线段树，不仅所用的空间小，实现起来的代码也比普通线段树短。
思想
动态开点线段树，顾名思义，就是一棵使用动态开点的线段树。（废话
在常用的堆式存储中，我们用 $ p \times 2 $ 和 $ p \times 2 + 1 $ 来表示节点 $ p $ 的两个儿子。而在动态开点线段树中，我们用 $ lson $ 和 $ rson $ 两个数组来记录每个节点的两个儿子的编号。并且 节点只有在被用到的时候才创建。这样，我们就能有效避免冗余空间的出现。
在修改时，如果我们发现当前节点并没有在线段树上，那么我们就创建这个节点。
模板（区间修改）
void modify(int &p, int L, int R, int l, int r, int c) {//L，R表示当前节点所包含的区间，l, r表示修改区间
//注意到是&p，这样可以使得上一层递归中不用再次手动修改传入的节点
if(!p) p = ++tot;//创建新节点
if(l <= L && R <= r) {
······//修改
return ;
}
pushdown(p, L, R);
int mid = L + R >> 1;
if(l <= mid) modify(t[p].ls, L, mid, l, r, c);
if(r > mid) modify(t[p].rs, mid + 1, R, l, r, c);
pushup(p);
}
在询问时，如果当前节点并未被创建，那么就可以返回 $ 0 $ 。这是因为如果当前节点没有被创建，说明这个区间没有被修改过，换句话说，这个区间所维护的东西不存在，即为 $ 0 $。
模板（区间查询）
int query(int p, int L, int R, int l, int r) {
if(!p) return 0;
if(l <= L && R <= r) return ···;//返回区间所维护的东西
pushdown(p, L, R);
int mid = L + R >> 1, res = 0;
if(l <= mid) ···; //查询并更新
if(r > mid) ···;
return res;
}
如果线段树上有初值的话，我们可以将其看做若干个修改。这样就不用写 $ build $ 函数了。
例题
$ \color {skyblue} P3372 【模板】线段树 1 $
题意
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 $ k $。
- 求出某区间每一个数的和。
思路
线段树维护
代码
#include<bits/stdc++.h>
#define int long long
#define Debug puts("Oops!")
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, m;
struct Node {
int ls, rs;
int lazy, dat;
};
struct Segment_Tree {
int root, tot;
Node t[N << 1];
void pushup(int p) {t[p].dat = t[t[p].ls].dat + t[t[p].rs].dat;}
void pushdown(int p, int l, int r) {
if(!t[p].ls) t[p].ls = ++tot;
if(!t[p].rs) t[p].rs = ++tot;
t[t[p].ls].lazy += t[p].lazy;
t[t[p].rs].lazy += t[p].lazy;
int mid = l + r >> 1;
t[t[p].ls].dat += t[p].lazy * (mid - l + 1);
t[t[p].rs].dat += t[p].lazy * (r - mid);
t[p].lazy = 0;
}
void add(int &p, int L, int R, int l, int r, int c) {
if(!p) p = ++tot;
if(l <= L && R <= r) {
t[p].dat += c * (R - L + 1);
t[p].lazy += c;
return ;
}
pushdown(p, L, R);
int mid = L + R >> 1;
if(l <= mid) add(t[p].ls, L, mid, l, r, c);
if(r > mid) add(t[p].rs, mid + 1, R, l, r, c);
pushup(p);
}
int query(int p, int L, int R, int l, int r) {
if(!p) return 0;
if(l <= L && R <= r) return t[p].dat;
pushdown(p, L, R);
int mid = L + R >> 1, res = 0;
if(l <= mid) res += query(t[p].ls, L, mid, l, r);
if(r > mid) res += query(t[p].rs, mid + 1, R, l, r);
return res;
}
}st;
inline int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
return x * f;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read();
for(int i = 1, x; i <= n; i++) {
x = read();
st.add(st.root, 1, n, i, i, x);
}
while(m--) {
int op = read(), l = read(), r = read();
if(op == 1) {
int x = read();
st.add(st.root, 1, n, l, r, x);
}
else {
cout << st.query(st.root, 1, n, l, r) << endl;
}
}
return 0;
}