线段树

1 线段树概念

线段树 $(SegmentTree)$ 是 $OI$ 中的常用算法。线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。且时间复杂度仅 $\Theta (\log n)$。

2 线段树操作

2.1 建树

对于一个区间，我们可以把它用线段树存储。可以把区间 $[1,4]$ 用如图所示的方式存储：

也就是说，如果要求 $[1,4]$ 的区间和，就可以通过把这个节点的两个儿子 $[1,2]$ 和 $[3,4]$ 的权值相加得到。推导到一般式，即

$$tre{e}_i.sum=tre{e}_{i\times 2}.sum+tre{e}_{i\times 2+1}.sum$$

struct segment_tree{int sum, tag = 0, l, r;
}tree[N << 2];
inline void build(int i, int l, int r) {tree[i].l = l, tree[i].r = r;if (l == r) {tree[i].sum = a[l];return;} int mid = (l + r) >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

注意线段树要开四倍空间。

2.2 区间修改

对给定区间每个数增加 $k$。这个似乎有一点棘手，我们可以引入一个新的懒标记$(LazyTag)$。一个点的懒标记代表它的区间上所有点应当做出的修改。

以 $\text{§}1$ 中的图为例，例如修改 $[1,3]$ 的值，从 $[1,4]$ 向下找，它的左儿子 $[1,2]$ 显然包含在所要修改的区间之内；它的右儿子 $[3,4]$ 区间过大，从它的左儿子接着找：$[3,3]$ 在区间中，而 $[4,4]$ 不在区间中。所以，只需要把 $[1.2]$ 和 $[3,3]$ 标记。

推导到一般地，如果区间包含在修改区间中，那么它需要打标记；如果不包含，考虑儿子：左儿子在区间中，找左儿子；右儿子在区间中，找右儿子。

如果单纯这样想，显然有一个巨大的纰漏：比如我们修改了 $[1,3]$，然后通过查询操作查询了 $[1,3]$ 的区间和，没有问题；但如果此时查询 $[2,4]$，因为 $[2,2]$ 没有被打标记，所以会少加一个 $k$。

对于一个区间，如果整个区间都要修改，那么首先把点的权值增加 $k\times (tre{e}_i.r-tre{e}_i.l+1)$。如果并不是都要修改，这时我们需要一个pushdown操作。所谓pushdown，就是把自己的懒标记清零，再给自己的儿子标记上。

inline void pushdown(int i) {if (tree[i].tag) {tree[i << 1].tag += tree[i].tag;tree[i << 1 | 1].tag += tree[i].tag;tree[i << 1].sum += tree[i].tag * (tree[i << 1].r - tree[i << 1].l + 1);tree[i << 1 | 1].sum += tree[i].tag * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1);tree[i].tag = 0;}
}

其他的 $tag$ 不为 $0$ 的区间在后面区间查询的时候顺便更新即可。区间修改的代码：

inline void add(int i, int l, int r, int k) {if (tree[i].l >= l && tree[i].r <= r) {tree[i].sum += k * (tree[i].r - tree[i].l + 1);tree[i].tag += k;return;}pushdown(i);if (tree[i << 1].r >= l) add(i << 1, l, r, k);if (tree[i << 1 | 1].l <= r)add(i << 1 | 1, l, r, k);tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}

2.3 区间查询

思路类似，注意pushdown即可。

inline int search(int i, int l, int r) {if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;pushdown(i);int ans = 0;if (tree[i << 1].r >= l) ans += search(i << 1, l, r);if (tree[i << 1 | 1].l <= r)ans += search(i << 1 | 1, l, r);return ans;
}

2.4 练习题目

【练习 2.1】P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态

题解

线段树模板题（注意要开 $\text{long long}$）。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n, m, a[N];
struct segment_tree{ll sum, tag = 0, l, r;
}tree[N << 2];
inline void build(ll i, ll l, ll r) {tree[i].l = l, tree[i].r = r;if (l == r) {tree[i].sum = a[l];return;} ll mid = (l + r) >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}
inline void pushdown(ll i) {if (tree[i].tag) {tree[i << 1].tag += tree[i].tag;tree[i << 1 | 1].tag += tree[i].tag;tree[i << 1].sum += tree[i].tag * (tree[i << 1].r - tree[i << 1].l + 1);tree[i << 1 | 1].sum += tree[i].tag * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1);tree[i].tag = 0;}
}
inline void add(ll i, ll l, ll r, ll k) {if (tree[i].l >= l && tree[i].r <= r) {tree[i].sum += k * (tree[i].r - tree[i].l + 1);tree[i].tag += k;return;}pushdown(i);if (tree[i << 1].r >= l) add(i << 1, l, r, k);if (tree[i << 1 | 1].l <= r)add(i << 1 | 1, l, r, k);tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
}
inline ll search(ll i, ll l, ll r) {if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;pushdown(i);ll ans = 0;if (tree[i << 1].r >= l) ans += search(i << 1, l, r);if (tree[i << 1 | 1].l <= r)ans += search(i << 1 | 1, l, r);return ans;
}
int main() {cin >> n >> m;for (ll i = 1; i<= n; i++) cin >> a[i];build(1, 1, n);while (m--) {ll op, x, y, k;cin >> op;if (op == 1) {cin >> x >> y >> k;add(1, x, y, k);} else {cin >> x >> y;cout << search(1, x, y) << endl;}}return 0;
}

3 线段树进阶

3.1 乘法线段树

如果线段树只有乘法操作，那么只要让懒标记变成乘法，然后 tree[i].sum *= k 即可。

但如果是有乘法也有加法，我们需要考虑先加还是先乘。

把懒标记分成加法标记 $(plz)$ 和乘法标记 $(mlz)$。对于 $mlz$，直接乘上父亲的标记即可，而对于 $plz$，需要把原先的 $plz$ 乘上父亲的 $mlz$ 再加上父亲的 $plz$。

【练习 3.1】P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态

题解

乘法线段树模板题（注意要开 $\text{long long}$ 和取模）。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n, m, q, a[N];
struct segment_tree{ll sum, plz, mlz, l, r;
}tree[N << 2];
inline ll mod(ll x){return (x % m + m) % m;
}
inline void build(ll i, ll l, ll r) {tree[i].l = l, tree[i].r = r;tree[i].plz = 0, tree[i].mlz = 1;if (l == r) {tree[i].sum = a[l];return;} ll mid = (l + r) >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline void pushdown(ll i) {if (tree[i].plz == 0 && tree[i].mlz == 1) return;int mlz0 = tree[i].mlz, plz0 = tree[i].plz;tree[i << 1].sum = mod(tree[i << 1].sum * mlz0 + plz0 * (tree[i << 1].r - tree[i << 1].l + 1));tree[i << 1].mlz = mod(tree[i << 1].mlz * mlz0);tree[i << 1].plz = mod(tree[i << 1].plz * mlz0 + plz0);tree[i << 1 | 1].sum = mod(tree[i << 1 | 1].sum * mlz0 + plz0 * (tree[i << 1 | 1].r - tree[i << 1 | 1].l + 1));tree[i << 1 | 1].mlz = mod(tree[i << 1 | 1].mlz * mlz0);tree[i << 1 | 1].plz = mod(tree[i << 1 | 1].plz * mlz0 + plz0);tree[i].mlz = 1, tree[i].plz = 0;
}
inline void add1(ll i, ll l, ll r, ll k) {if (tree[i].l >= l && tree[i].r <= r) {tree[i].sum = mod(tree[i].sum * k);tree[i].mlz = mod(tree[i].mlz * k);tree[i].plz = mod(tree[i].plz * k);return;}pushdown(i);if (tree[i << 1].r >= l) add1(i << 1, l, r, k);if (tree[i << 1 | 1].l <= r)add1(i << 1 | 1, l, r, k);tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline void add2(ll i, ll l, ll r, ll k) {if (tree[i].l >= l && tree[i].r <= r) {tree[i].sum = mod(tree[i].sum + k * (tree[i].r - tree[i].l + 1));tree[i].plz = mod(tree[i].plz + k);return;}pushdown(i);if (tree[i << 1].r >= l) add2(i << 1, l, r, k);if (tree[i << 1 | 1].l <= r)add2(i << 1 | 1, l, r, k);tree[i].sum = mod(tree[i << 1].sum + tree[i << 1 | 1].sum);
}
inline ll search(ll i, ll l, ll r) {if (tree[i].l >= l && tree[i].r <= r) return tree[i].sum;pushdown(i);ll ans = 0;if (tree[i << 1].r >= l) ans = mod(ans + search(i << 1, l, r));if (tree[i << 1 | 1].l <= r)ans = mod(ans + search(i << 1 | 1, l, r));return ans;
}
int main() {cin >> n >> q >> m;for (ll i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);while (q--) {ll op, x, y, k;cin >> op;if (op == 1) {cin >> x >> y >> k;add1(1, x, y, k);}else if (op == 2) {cin >> x >> y >> k;add2(1, x, y, k);} else {cin >> x >> y;cout << search(1, x, y) << endl;}}return 0;
}

* 补充：快读快写

模板如下：

template<typename T>inline void read(T &x) {bool f = 1;x = 0;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = !f;ch = getchar(); }while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}x = (f ? x : -x);return;
}
template<typename T>inline void write(T x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');return;
}

快写不如printf和优化过的cout快，所以还是建议使用prinf。

4 End

参考文章：

• 线段树 从入门到进阶（超清晰，简单易懂）_进阶线段树-CSDN博客

• 线段树_百度百科

感谢yes_NT和Happy_WA_Day同学的指导。