1. 什么是线段树

顾名思义 ， 线段树是一棵二叉树 ， 但不同的是这棵树的结点储存的值是一个数列中 $[l,r]$ 的某个需要的值 （例如，求和，求最大值，求最小值）

这是一棵典型的线段树 ，其性质是 ：

若其中一子节点编号为 $a$，则该节点左儿子编号为 $2a$，其右儿子编号为 $2a+1$

且它的父结点的编号为 $\frac{\mathbf{a}}{2}$（c++语言中除法只取整数部分）。

2. 线段树的用处

线段树的用处就是，对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是 $O(lo{g}_{2}n)$.

3. 线段树的模板题

• 线段树（单点修改，区间查询）

• 线段树（区间修改 ， 单点查询）

• 线段树（区间修改，区间查询）

• 维护序列

  对于一个长度为 $N$ 的序列 $a$ 支持以下操作

  1.令所有满足 $l<=i<=r$ 的 $a_i$ 全部变为 $a_i\ast c$ 。

  2.令所有满足 $l<=i<=r$ 的 $ai$ 全部变为 $a_i+c$ 。

  3.求所有满足 $l<=i<=r$ 的 $a_i$ 的和。

  显然这是对一个区间做加法和乘法的操作，可以使用线段树完成。

  因为乘的运算级别比加法高，所以在做加法是不用管乘法，在做乘法时要管加法。只要理解了这点，程序就能看懂了

  $ACcode$

注意要加快读

#include <bits/stdc++.h>
using namespace std;#define lw(o) o << 1
#define rw(o) o << 1 | 1
const int maxn = 1e5 + 5;struct kk
{long long mul, sum, add;} tr[maxn << 2];int n, M, a[maxn], op, x, y, m;inline void push_up(int t)
{tr[t].sum = (tr[lw(t)].sum + tr[rw(t)].sum) % M;}void build(int o, int l, int r)
{tr[o].mul = 1;if (l == r){tr[o].sum = a[l];return;}int mid = (l + r) >> 1;build(lw(o), l, mid);build(rw(o), mid + 1, r);push_up(o);
}void push_down(int t, int k)
{tr[t << 1].sum = (tr[t << 1].sum * tr[t].mul + tr[t].add * (k + 1 >> 1)) % M;tr[t << 1 | 1].sum = (tr[t << 1 | 1].sum * tr[t].mul + tr[t].add * (k >> 1)) % M;tr[t << 1].mul = tr[t << 1].mul * tr[t].mul % M;tr[t << 1 | 1].mul = tr[t << 1 | 1].mul * tr[t].mul % M;tr[t << 1].add = (tr[t << 1].add * tr[t].mul + tr[t].add) % M;tr[t << 1 | 1].add = (tr[t << 1 | 1].add * tr[t].mul + tr[t].add) % M;tr[t].mul = 1;tr[t].add = 0;
}void cheng(int o, int l, int r, long long val)
{if (x <= l && r <= y){tr[o].mul = tr[o].mul * val % M;tr[o].add = tr[o].add * val % M;tr[o].sum = tr[o].sum * val % M;return;}push_down(o, r - l + 1);int mid = (l + r) >> 1;if (x <= mid){cheng(lw(o), l, mid, val);}if (mid < y){cheng(rw(o), mid + 1, r, val);}push_up(o);
}void jia(int o, int l, int r, long long val)
{if (x <= l && r <= y){tr[o].add = (tr[o].add + val) % M;tr[o].sum = (tr[o].sum + (r - l + 1) * val) % M;return;}push_down(o, r - l + 1);int mid = (l + r) >> 1;if (x <= mid){jia(lw(o), l, mid, val);}if (mid < y){jia(rw(o), mid + 1, r, val);}push_up(o);
}long long query(int o, int l, int r)
{if (x <= l && r <= y){return tr[o].sum;}push_down(o, r - l + 1);int mid = (l + r) >> 1;long long ans = 0;if (x <= mid){ans += query(lw(o), l, mid);}if (mid < y){ans += query(rw(o), mid + 1, r);}if (ans >= M){ans -= M;}push_up(o);return ans;
}signed main()
{cin >> n >> M;for (int i = 1; i <= n; i++){cin >> a[i];}build(1, 1, n);cin >> m;while (m--){int a, b;cin >> op >> x >> y;if (op == 1){cin >> a;cheng(1, 1, n, a);}if (op == 2){cin >> b;jia(1, 1, n, b);}if (op == 3){cout << query(1, 1, n) << endl;}}return 0;
}

4. 动态开点线段树

通常来说，线段树占用空间是总区间长 $n$ 的常数倍，空间复杂度是 $O(4n)$ 。然而，有时候 $n$ 很巨大，而我们又不需要使用所有的节点，这时便可以动态开点——不再一次性建好树，而是一边修改、查询一边建立。我们不再用 $p\ast 2$ 和 $p\ast 2+1$ 代表左右儿子，而是用两个数组 $L[]$ 和 $R[]$ 记录左右儿子的编号。设总查询次数为 $m$ ，则这样的总空间复杂度为 $O(mlogn)$ 。

比起普通线段树，动态开点线段树有一个优势：它能够处理零或负数位置。此时，求 $mid$ 时不能用 $(cl+cr)/2$ ，而要用 $(cl+cr-1)/2$ （因为 $cl$ 等于 $cr$ 时会退出递归）

因为缓存命中等原因，动态开点线段树写成结构体形式速度往往更快一些。不过 $tree[tree[p].ls].val$ 之类的写法怎么看都很反人类 繁琐，所以我一般会用宏简化一下。

// MAXV一般能开多大开多大，例如内存限制128M时可以开到八百万左右
namespace SegTree
{
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
#define mark(x) tree[x].mark
using T = int;
const int MAXV = 1.6e7, L = 1, R = 1e9;
const T NA = -2e9;
int cnt = 1;
struct node
{T val, mark = NA;int ls, rs;
} tree[MAXV];
T op(T a, T b)
{return a + b;
}
void upd(int p, T d, int len)
{val(p) += d * len;mark(p) += d;
}
void push_down(int p, int len)
{if (!ls(p)) ls(p) = ++cnt; // 左儿子不存在，创建新节点if (!rs(p)) rs(p) = ++cnt; // 右儿子不存在，创建新节点if (mark(p) != NA){upd(ls(p), mark(p), len / 2);upd(rs(p), mark(p), len - len / 2);mark(p) = NA;}
}
void update(int l, int r, T d, int p = 1, int cl = L, int cr = R)
{if (cl >= l && cr <= r)return upd(p, d, cr - cl + 1);push_down(p, cr - cl + 1);int mid = (cl + cr - 1) / 2;if (mid >= l)update(l, r, d, ls(p), cl, mid);if (mid < r)update(l, r, d, rs(p), mid + 1, cr);val(p) = op(val(ls(p)), val(rs(p)));
}
T query(int l, int r, int p = 1, int cl = L, int cr = R)
{if (cl >= l && cr <= r)return val(p);push_down(p, cr - cl + 1);int mid = (cl + cr - 1) / 2;if (mid >= r)return query(l, r, ls(p), cl, mid);else if (mid < l)return query(l, r, rs(p), mid + 1, cr);elsereturn op(query(l, r, ls(p), cl, mid), query(l, r, rs(p), mid + 1, cr));
}
#undef ls
#undef rs
#undef val
#undef mark
}; // namespace SegTree

可以看到，除了在 $pus{h}_{d}own$ 中进行了新节点的创建，其他基本和普通线段树一致。动态开点线段树不需要 $build$ ，通常用在没有提供初始数据的场合（例如初始全 $0$ ），这时更能显示出优势，例如 $CF915E$（这道题因为是赋值，也可以使用珂朵莉树）。

当然，除了动态开点，其实先离散化再建树也常常能达到效果。但动态开点写起来更简单直观，而且在强制在线时只能这样做。

5. 权值线段树

桶我们经常使用，例如计数排序时用 $cnt$ 数组记录每个数出现的次数。权值线段树就是用线段树维护一个桶，它可以 $O(logv)$ （ $v$ 为值域）地查询某个范围内的数出现的总次数。不仅如此，它还可以 $O(logv)$ 地求得第 $k$ 大的数。事实上，它常常可以代替平衡树使用。

由于权值线段树需要按值域开空间，所以常常动态开点。

// MAXV一般能开多大开多大，例如内存限制128M时可以开到八百万左右
namespace SegTree
{
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
using T = int;
const int MAXV = 8e6, L = -1e7, R = 1e7; // 值域为[L, R]
const T NA = -2e9;
int cnt = 1;
struct node
{T val;int ls, rs;
} tree[MAXV];
T op(T a, T b)
{return a + b;
}
void upd(int p, T d, int len)
{val(p) += d * len;
}
void push_down(int p)
{if (!ls(p)) ls(p) = ++cnt;if (!rs(p)) rs(p) = ++cnt;
}
void update(int x, T d, int p = 1, int cl = L, int cr = R) // 单点修改
{if (cl == cr)return upd(p, d, 1);push_down(p);int mid = (cl + cr - 1) / 2;if (x <= mid)update(x, d, ls(p), cl, mid);elseupdate(x, d, rs(p), mid + 1, cr);val(p) = op(val(ls(p)), val(rs(p)));
}
T query(int l, int r, int p = 1, int cl = L, int cr = R)
{if (cl >= l && cr <= r)return val(p);push_down(p);int mid = (cl + cr - 1) / 2;if (mid >= r)return query(l, r, ls(p), cl, mid);else if (mid < l)return query(l, r, rs(p), mid + 1, cr);elsereturn op(query(l, r, ls(p), cl, mid), query(l, r, rs(p), mid + 1, cr));
}
void insert(int v) // 插入
{update(v, 1);
}
void erase(int v) // 删除
{update(v, -1);
}
int countl(int v)
{return query(L, v - 1);
}
int countg(int v)
{return query(v + 1, R);
}
int rank(int v) // 求排名
{return countl(v) + 1;
}
int kth(int k, int p = 1, int cl = L, int cr = R) // 求指定排名的数
{if (cl == cr)return cl;int mid = (cl + cr - 1) / 2;if (val(ls(p)) >= k)return kth(k, ls(p), cl, mid); // 往左搜elsereturn kth(k - val(ls(p)), rs(p), mid + 1, cr); // 往右搜
}
int pre(int v) // 求前驱
{int r = countl(v);return kth(r);
}
int suc(int v) // 求后继
{int r = val(1) - countg(v) + 1;return kth(r);
}
#undef ls
#undef rs
#undef val
#undef mark
}; // namespace SegTree

代替平衡树使用时，权值线段树代码比较短，但是当值域较大、询问较多时空间占用会比较大。

5. 可持久化线段树

可持久化线段树，也叫主席树。

可持久化数据结构思想，就是保留整个操作的历史，即，对一个线段树进行操作之后，保留访问操作前的线段树的能力。

最简单的方法，每操作一次，建立一颗新树。这样对空间的需求会很大。

而注意到，对于点修改，每次操作最多影响 $\lfloor {\log }_2(n-1)\rfloor +2$ 个节点，于是，其实操作前后的两个线段树，结构一样，

而且只有 $\lfloor {\log }_2(n-1)\rfloor +2$ 个节点不同，其余的节点都一样，于是可以重复利用其余的点。

这样，每次操作，会增加 $\lfloor {\log }_2(n-1)\rfloor +2$ 个节点。

于是，这样的线段树，每次操作需要 $O({\log }_2(n))$ 的空间。

对于每一个版本的线段树，用 $rt$ 数组记录它的根节点就行了。

例题

对于本题，必须先将数据进行离散化。

然后我们逐一插入数字。

将每个数字的大小（即离散化后的编号）插入到它的位子上，然后并把所有包括它的区间的 $sum$ 都加 $1$。

若有 $n$ 个数，则有 $n$ 个版本的主席树。

假设读入 $1、5、2、4$。

现在要查询 $[2,5]$ 中第 $3$ 大的数，我们首先把第 $1$ 棵线段树和第 $5$ 棵拿出来。

然后我们发现，将对应节点的数相减，刚刚好就是 $[2,5]$ 内某个范围内的数的个数。比如 $[1,4]$ 这个节点相减是 $2$，就说明$[2,5]$ 内有 $2$ 个数是在 $14$ 范围内（就是 $2,3$）。

所以对于一个区间 $[l,r]$，我们可以每次算出在 $[l,mid]$ 范围内的数，如果数量 $>=k$（ $k$ 就是第 $k$ 大），就往左子树走，否则就往右子树走。

AC CODE

#include <bits/stdc++.h>
#define _ 200010
using namespace std;int l, r, k, q, ans;
int cnt_node, n, m;
int sum[_ << 5], rt[_], lc[_ << 5], rc[_ << 5];
int a[_], b[_];
int p;void build(int &t, int l, int r)
{t = ++cnt_node;if (l == r)return;int mid = (l + r) >> 1;build(lc[t], l, mid);build(rc[t], mid + 1, r);
}int modify(int o, int l, int r)
{int oo = ++cnt_node;lc[oo] = lc[o];rc[oo] = rc[o];sum[oo] = sum[o] + 1;if (l == r)return oo;int mid = (l + r) >> 1;if (p <= mid)lc[oo] = modify(lc[oo], l, mid);elserc[oo] = modify(rc[oo], mid + 1, r);return oo;
}int query(int u, int v, int l, int r, int k)
{int ans, mid = ((l + r) >> 1), x = sum[lc[v]] - sum[lc[u]];if (l == r)return l;if (x >= k)ans = query(lc[u], lc[v], l, mid, k);elseans = query(rc[u], rc[v], mid + 1, r, k - x);return ans;
}signed main()
{scanf("%d%d", &n, &m);for (register int i = 1; i <= n; i += 1)scanf("%d", &a[i]), b[i] = a[i];sort(b + 1, b + n + 1);q = unique(b + 1, b + n + 1) - b - 1;build(rt[0], 1, q);for (register int i = 1; i <= n; i += 1){p = lower_bound(b + 1, b + q + 1, a[i]) - b;rt[i] = modify(rt[i - 1], 1, q);}while (m--){scanf("%d%d%d", &l, &r, &k);ans = query(rt[l - 1], rt[r], 1, q, k);printf("%d\n", b[ans]);}return 0;
}