引入
用来维护区间信息的数据结构
可以在 \(O(\log N)\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值、最小值）等操作。
线段树的基本结构与建树
过程
将每个长度不为 \(1\) 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。
在实现时，我们考虑递归建树。设当前的根节点为 \(p\)，如果根节点管辖的区间长度已经是 \(1\)，则可以直接根据 \(a\) 数组上相应位置的值初始化该节点。否则我们将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。
实现
void build(int rt， int l, int r) {
//对 [l, r] 区间建立线段树，当前根的编号为 p
if (l == r) {
tr[rt] = a[l];
return;
}
int mid = l + ((r - l) >> 1);
//移位运算符的优先级小于加减法，所以加上括号
//如果写成 (l + r) >> 1 可能会超出 int 范围
build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
线段树的空间：如果采用堆式存储（\(2p\) 是 \(p\) 的左儿子，\(2p + 1\) 是 \(p\) 的右儿子），若有 \(n\) 个叶子节点，则 \(tr\) 数组的范围最大为 \(2^{\lceil \log n \rceil + 1}\)。
分析：容易知道线段树的深度是 \(\lceil \log n \rceil\) 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 \(2^{\lceil \log n \rceil}\) 个，又由于其为一棵完全二叉树，则其总节点个数为 \(2^{\lceil \log n \rceil + 1} - 1\)。当然，可以直接把数组长度设为 \(4n\)，因为 \(\frac{2^{\lceil \log n \rceil + 1} - 1}{n}\) 的最大值在 \(n = 2^x + 1(x \in N_+)\) 时取到，此时节点数为 \(2^{\lceil \log n \rceil + 1} - 1 = 2^{x + 2} - 1 = 4n - 5\)。
线段树的区间查询
过程
区间查询，比如求区间 \([l, r]\) 的总和（即 \(a_l + a_{l + 1} + \cdots + a_r\)）、求区间最大值/最小值等操作。
一般地，如果要查询的区间是 \([l, r]\)，则可以将其拆成最多为 \(O(\log n)\) 个极大的区间，合并这些区间即可求出 \([l, r]\) 的答案。
实现
int query(int l, int r, int rt, int L, int R) {
//[L, R] 为查询区间，[l, r] 为当前节点包含的区间，rt 为当前节点的编号
if (L <= l && r <= R) return tr[rt];
//当前区间为询问区间的子集时直接返回当前区间的和
int mid = l + ((r - l) >> 1), sum = 0;
if (L <= mid) sum += query(l, mid, rt << 1, L, R);
//如果左儿子代表的区间 [l, mid] 与询问区间有交集，则递归查询左儿子
if (R > mid) sum += query(mid + 1, r, rt << 1 | 1, L, R);
//如果右儿子代表的区间 [mid + 1, r] 与询问区间有交集，则递归查询右儿子
return sum;
}
线段树的区间修改与懒惰标记
过程
懒惰标记，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方式表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点信息。实质性的修改则在下一次访问带有标记的节点时进行。
实现
区间修改（区间加上某个值）：
void update(int l, int r, int rt, int L, int R, int k) {//k 为被修改元素的变化量
if (L <= l && r <= R) {
tr[rt] += (r - l + 1) * k, lazy[rt] += k;
return;
}//当前区间为修改区间的子集时直接修改当前节点的值，然后打标记，结束修改
int mid = l + ((r - l) >> 1);
if (lazy[rt] && l != r) {
//如果当前节点的懒标记非空，则更新当前节点两个子节点的值的懒标记值
tr[rt << 1] += lazy[rt] * (mid - l + 1), tr[rt << 1 | 1] += lazy[rt] * (r - mid);
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];//将标记下传给子节点
lazy[rt] = 0;//清空当前节点的标记
}
if (L <= mid) update(l, mid, rt << 1, L, R, k);
if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R, k);
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
区间查询（区间求和）：
int query(int l, int r, int rt, int L, int R) {
if (L <= l && r <= R) return tr[rt];
int mid = l + ((r - l) >> 1);
if (lazy[rt]) {
//如果当前节点的懒标记非空，则更新当前节点两个子节点的值和懒标记值
tr[rt << 1] += lazy[rt] * (mid - l + 1), tr[rt << 1 | 1] += lazy[rt] * (r - mid);
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] + lazy[rt];
lazy[rt] = 0;
}
int sum = 0;
if (L <= mid) sum += query(l, mid, rt << 1, L, R);
if (R > mid) sum += query(mid + 1, r, rt << 1 | 1, L, R);
return sum;
}
如果要实现区间修改为某一个值而不是加上某一个值的话：
void update(int l, int r, int rt, int L, int R, int k) {
if (L <= l && r <= R) {
tr[rt] = (r - l + 1) * k, lazy[rt] = k;
return;
}
int mid = l + ((r - l) >> 1);
//额外数组储存是否修改值
if (v[rt]) {
tr[rt << 1] = lazy[rt] * (mid - l + 1), tr[rt << 1 | 1] = lazy[rt] * (r - mid);
lazy[rt << 1] = lazy[rt << 1] = lazy[rt];
v[rt << 1] = v[rt << 1 | 1] = 1;
v[rt] = 0;
}
if (L <= mid) update(l, mid, rt << 1, L, R, k);
if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R, k);
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
int query(int l, int r, int rt, int L, int R) {
if (L <= l && r <= R) return tr[rt];
int mid = l + ((r - l) >> 1);
if (v[rt]) {
tr[rt << 1] = lazy[rt] * (mid - l + 1), tr[rt << 1 | 1] = lazy[rt] * (r - mid);
lazy[rt << 1] = lazy[rt << 1] = lazy[rt];
v[rt << 1] = v[rt << 1 | 1] = 1;
v[rt] = 0;
}
int sum = 0;
if (L <= mid) sum += query(l, mid, rt << 1, L, R);
if (R > mid) sum += query(mid + 1, r, rt << 1 | 1, L, R);
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
return sum;
}
动态开点线段树
在堆式储存的情况下，需要给线段树开 \(4n\) 大小的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根节点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子节点。这样我们不再使用 \(2p\) 和 \(2p + 1\) 代表 \(p\) 节点的儿子，而是用 \(ls\) 和 \(rs\) 记录儿子的编号。总之，动态开点线段树的核心思想就是：节点只有在有需要的时候才被创建。
单次操作的时间复杂度是不变的，为 \(O(\log n)\)。由于每次操作都有可能创建并访问全新的一系列节点，因此 \(m\) 次单点操作后节点的数量规模是 \(O(m \log n)\)。最多也只需要 \(2n - 1\) 个节点，没有浪费。
单点修改：
//root 表示整棵线段树的根节点，cnt 表示当前节点个数（编号）
int n, cnt, root;
int sum[n << 1], ls[n << 1], rs[n << 1];
//用法：update(root, 1, n, x, f); 其中 x 为待修改的节点的编号
void update(int &p, int l, int s, int x, int f) {
if (!p) p = ++cnt;//当节点为空时，创建一个新的节点
if (l == r) {
sum[p] += f;
return;
}
int mid = l + ((r - l) >> 1);
if (x < mid) update(ls[p], l, mid, x, f);
else update(rs[p], mid + 1, l, x, f);
sum[p] = sum[ls[p]] + sum[rs[p]];//pushup
}
区间询问：
int query(int p, int l, int r, int L, int R) {
if (!p) return 0;//如果节点为空，返回 0
if (L <= l && r <= R) return sum[p];
int mid = l + ((r - l) >> 1), ans = 0;
if (L <= mid) ans += query(ls[p], l, mid, L, R);
if (R > m) ans += query(rs[p], mid + 1, r, L, R);
return ans;
}
区间修改也是一样的，不过下放标记时要注意如果缺少孩子，就直接创建一个新的孩子。或者使用标记永久化技巧。
一些优化
-
在叶子节点处无需下放懒标记，所以懒标记可以不下传到叶子节点。
-
下放懒标记可以写一个专门的函数
pushdown，从儿子节点更新当前节点也可以写一个专门的函数maintain（或者对称地用pushup），降低代码编写难度。 -
标记永久化：如果确定懒标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。
例题
区间加，区间求和。
#include <bits/stdc++.h>
#define ls rt << 1
#define rs rt << 1 | 1
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, tree[N << 2], lazy[N << 2], a[N];
void push_up(int rt) {
tree[rt] = tree[ls] + tree[rs];
}
void build(int rt, int l, int r) {
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(rt);
}
void f(int rt, int l, int r, int k) {
lazy[rt] = lazy[rt] + k;
tree[rt] = tree[rt] + k * (r - l + 1);
}
void push_down(int rt, int l, int r) {
int mid = (l + r) >> 1;
f(ls, l, mid, lazy[rt]);
f(rs, mid + 1, r, lazy[rt]);
lazy[rt] = 0;
}
void update(int l, int r, int rt, int L, int R, int k) {
if (L <= l && r <= R) {
tree[rt] += k * (r - l + 1);
lazy[rt] += k;
return;
}
push_down(rt, l, r);
int mid = (l + r) >> 1;
if (L <= mid) update(l, mid, ls, L, R, k);
if (R > mid) update(mid + 1, r, rs, L, R, k);
push_up(rt);
}
int query(int l, int r, int rt, int L, int R) {
if (L <= l && r <= R) return tree[rt];
push_down(rt, l, r);
int res = 0;
int mid = (l + r) >> 1;
if (L <= mid) res += query(l, mid, ls, L, R);
if (R > mid) res += query(mid + 1, r, rs, L, R);
return res;
}
int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * w;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) write(x / 10);
putchar(x % 10 ^ '0');
}
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i ++ ) a[i] = read();
build(1, 1, n);
while (m--) {
int op = read();
if (op == 1) {
int x = read(), y = read(), k = read();
update(1, n, 1, x, y, k);
} else {
int x = read(), y = read();
write(query(1, n, 1, x, y)), puts("");
}
}
return 0;
}
区间加、乘，区间求和。
注意加法和乘法的先后顺序。
#include <bits/stdc++.h>
#define ls rt << 1
#define rs rt << 1 | 1
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, b, x, y, k, a[N << 2], sum[N << 2], lazy[N << 2], tagc[N << 2], taga[N << 2];
int mod;
void push_up(int rt) {
sum[rt] = sum[ls] + sum[rs];
}
void build(int l, int r, int rt) {
tagc[rt] = 1;
if (l == r) {
sum[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
push_up(rt);
}
void push_down(int rt, int l, int r) {//taga:add,tagc:乘
//乘法优先
if(tagc[rt] != 1) {
int t = tagc[rt];
tagc[ls] = tagc[ls] * t % mod, sum[ls] = sum[ls] * t % mod;
tagc[rs] = tagc[rs] * t % mod, sum[rs] = sum[rs] * t % mod;
taga[ls] = taga[ls] * t % mod;
taga[rs] = taga[rs] * t % mod;
tagc[rt] = 1;
}
if(taga[rt]) {
int t = taga[rt];
int mid = (l + r) >> 1;
taga[ls] = (taga[ls] + t) % mod;
taga[rs] = (taga[rs] + t) % mod;
sum[ls] = (sum[ls] + (mid - l + 1) * t) % mod;
sum[rs] = (sum[rs] + (r - mid) * t) % mod;
taga[rt] = 0;
}
}
void change(int ll,int rr,int ql,int qr,int rt,int v,int t) {
if (ll > qr || rr < ql) return;
if (ql <= ll && rr <= qr) {
if (t == 0) taga[rt] = (taga[rt] + v) % mod, sum[rt] = (sum[rt] + 1ll * (rr - ll + 1) * v) % mod;
else tagc[rt] = tagc[rt] * v % mod, taga[rt] = taga[rt] * v % mod, sum[rt] = sum[rt] * v % mod;
return;
}
push_down(rt, ll, rr);
int mid = (ll + rr) >> 1;
change(ll, mid, ql, qr, ls, v, t), change(mid+1, rr, ql, qr, rs, v, t);
push_up(rt);
}
int query(int ll, int rr, int ql, int qr, int rt) {
if(ll > qr || rr < ql) return 0;
if(ql <= ll && rr <= qr) return sum[rt];
push_down(rt, ll, rr);
int mid = (ll + rr) >> 1;
return (query(ll, mid, ql, qr, ls) + query(mid + 1, rr, ql, qr, rs)) % mod;
}
signed main() {
cin >> n >> m >> mod;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
build(1, n, 1);
for (int i = 1; i <= m; i ++ ) {
cin >> b;
if (b == 1) {
cin >> x >> y >> k;
change(1, n, x, y, 1, k, 1);
} else if (b == 2) {
cin >> x >> y >> k;
change(1, n, x, y, 1, k, 0);
} else { //b==3
cin >> x >> y;
cout << query(1, n, x, y, 1) << endl;
}
}
return 0;
}
权值线段树
和普通线段树样子类似，但含义不同。线段树的节点存储该值域内的元素个数，其节点范围是一个值域。
维护“桶”的信息，即维护每个数出现的次数。
但是只能维护整个序列的第 \(k\) 大/小，若要维护区间 \([l, r]\) 的，需要用主席树（可持久化权值线段树）。
例如，构建权值线段树存储序列 \(\{3, 1, 4, 2, 3, 5, 3, 4\}\)，过程如下：
（1）该序列的最小值和最大值分别为 \(1\) 和 \(5\)，树根 \([1, 5]\) 表示值域大于或等于 \(1\) 小于或等于 \(5\)，下面的节点只需像构建普通线段树一样二分即可。初始化时，权值线段树每个节点的权值均为 \(0\)，即落入该节点值域内的元素个数为 \(0\)，如下图所示；然后将序列中的元素依次插入权值线段树中，每插入一个元素，即产生一棵权值线段树。
（2）将序列第 \(1\) 个元素 \(3\) 插入权值线段树，则落入值域 \([1, 5]\) 的数有 \(1\) 个，落入值域 \([1, 3]\) 的数有 \(1\) 个，落入值域 \([3, 3]\) 的数有 \(1\) 个。第 \(1\) 棵权值线段树如下图所示。
（3）依次插入元素 \(1、4、2、3\)，落入值域 \([1, 5]\) 的数有 \(5\) 个，落入值域 \([1, 3]\) 的数有 \(4\) 个，等等。第 \(5\) 棵权值线段树如下图所示。
（4）依次插入元素 \(5、3、4\)，落入值域 \([1, 5]\) 的数有 \(8\) 个，落入值域 \([1, 3]\) 的数有 \(5\) 个，等等。第 \(8\) 棵权值线段树如下图所示。
上面 \(n\) 棵权值线段树的形状一模一样，只是节点的权值不一样，所以这样的两棵线段树是可以相减的（两棵线段树相减就是每个对应节点的权值相减）。
第 \(8\) 棵权值线段树减去第 \(5\) 棵权值线段树得到的权值线段树如下图所示。第 \(5\) 棵权值线段树维护的序列区间是 \([1, 5]\)，第 \(8\) 棵权值线段树维护的序列区间是 \([1, 8]\)，两棵线段树相减得到一个新的序列区间 \([6,8]\)，即序列第 \(6～8\) 个元素 \(\{5, 3, 4\}\) 对应的权值线段树。
这里应用了前缀和的思想：若任意一个 \([l, r]\) 区间的权值线段树都可以由两棵权值线段树（\([1, r]\) 和 \([1, l - 1]\)）相减得到，则可以在这棵权值线段树上快速查询区间问题。
但是，这 \(n\) 棵权值线段树占用的空间太大了，其中有很多节点重复，浪费了大量空间。对此可以考虑优化：在创建权值线段树的过程中仅对权值有变化的节点进行新建，对权值未修改的节点直接重用，这就是可持久化线段树。
线段树合并
过程
线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护线段树上或是图上的信息。
我们需要使用上文的动态开点线段树。
过程：
假设两棵线段树为 \(A\) 和 \(B\)，我们从 \(1\) 号节点开始递归合并。
递归到某个节点时，如果 \(A\) 树或者 \(B\) 树上对应节点为空，直接返回另一个树上对应节点（动态开点线段树的特性）。
如果递归到叶子节点，我们合并两棵树上的对应节点。
最后，根据子节点更新当前节点并且返回。
复杂度：
显然，对于两棵满的线段树，合并操作的复杂度是 \(O(n\log n)\) 的。但实际情况下使用的常常是权值线段树，总点数和 \(n\) 的规模相差并不大。并且合并时一般不会重复地合并某个线段树，所以我们最终增加的点数大致是 \(n\log n\) 级别的。这样，总的复杂度就是 \(O(n\log n)\) 级别的。当然，在一些情况下，可并堆可能是更好的选择。
实现
int merge(int a, int b, int l, int r) {
if (!a || !b) return a | b;
if (a == v) {
// do something...
return a;
}
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
pushup(a);
return a;
}
例题
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
思路：用差分把树上修改转化为单点修改，然后向上 dfs 线段树合并统计答案即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10, N = maxn << 6;
#define mid (l+r>>1)
struct edge {
int to, nxt;
} e[maxn << 1];
int head[maxn], cnt, root[maxn];
void add(int u, int v) {
e[ ++ cnt] = (edge) {
v, head[u]
};
head[u] = cnt;
}
int f[maxn][22], dep[maxn];
bool vis[maxn];
void DFS(int x, int d) {
dep[x] = d;
vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt)
if (!vis[e[i].to]) f[e[i].to][0] = x, DFS(e[i].to, d + 1);
}
int ll[maxn];
void init(int n) {
for (int i = 2; i < maxn; i ++ ) ll[i] = ll[i >> 1] + 1;
for (int j = 1; j <= 20; j ++ )
for (int i = 1; i <= n; i ++ )
f[i][j] = f[f[i][j - 1]][j - 1];
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
while (dep[x] > dep[y]) x = f[x][ll[dep[x] - dep[y]]];
if (x == y) return x;
for (int i = 20; i >= 0; i -- )
if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int ls[N], rs[N], tot, mx[N], nb[N];
void pushup(int tr) {
if (mx[ls[tr]] >= mx[rs[tr]]) mx[tr] = mx[ls[tr]], nb[tr] = nb[ls[tr]];
else mx[tr] = mx[rs[tr]], nb[tr] = nb[rs[tr]];
}
void update(int &tr, int l, int r, int u, int v) {
if (!tr) tr = ++ tot;
if (l == r) return mx[tr] += v, nb[tr] = l, void();
if (u <= mid) update(ls[tr], l, mid, u, v);
else update(rs[tr], mid + 1, r, u, v);
pushup(tr);
}
int ans[maxn];
int merge(int now, int lst, int l, int r) {
if (!now || !lst) return now | lst;
if (l == r) {
mx[now] += mx[lst];
return now;
}
ls[now] = merge(ls[now], ls[lst], l, mid);
rs[now] = merge(rs[now], rs[lst], mid + 1, r);
pushup(now);
return now;
}
void dfs(int x) {
vis[x] = 1;
for (int i = head[x]; i; i = e[i].nxt)
if (!vis[e[i].to]) {
dfs(e[i].to);
root[x] = merge(root[x], root[e[i].to], 1, 1e5);
}
ans[x] = nb[root[x]];
if (!mx[root[x]]) ans[x] = 0;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i < n; i ++ ) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
DFS(1, 0);
init(n);
while (m--) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
int fa = lca(x, y);
update(root[x], 1, 1e5, k, 1);
update(root[y], 1, 1e5, k, 1);
update(root[fa], 1, 1e5, k, -1);
update(root[f[fa][0]], 1, 1e5, k, -1);
}
memset(vis, 0, sizeof(vis));
dfs(1);
for (int i = 1; i <= n; i ++ ) cout << ans[i] << endl;
return 0;
}
线段树分裂
过程
线段树分裂实质上是线段树合并的逆过程。线段树分裂只适用于有序的序列，无需的序列是没有意义的，常用在动态开点的权值线段树。
注意当分裂和合并都存在时，我们在合并时必须回收节点，以避免分裂时会可能出现节点重复占用的问题。
从一棵区间为 \([1, N]\) 的线段树中分裂出 \([l, r]\)，建一棵新的树：
从 \(1\) 号节点开始递归分裂，当节点不存在或者代表的区间 \([s, t]\) 与 \([l, r]\) 没有交集时直接回溯。
当 \([s, t]\) 与 \([l, r]\) 有交集时需要开一个新结点。
当 \([s, t]\) 包含于 \([l, r]\) 时，需要将当前结点直接接到新的树下面，并把旧边断开。
复杂度：
可以发现被断开的边最多只会有 \(\log n\) 条，所以最终每次分裂的时间复杂度就是 \(O(\log n)\)，相当于区间查询的复杂度。
实现
void split(int &tr, int &y, int l, int r, int L, int R) {
if (!tr) return y = 0, void();
if (L <= l && r <= R) return y = tr, tr = 0, void();
y = ++ tot;
if (L <= mid) split(ls[tr], ls[y], l, mid, L, R);
if (R > mid) split(rs[tr], rs[y], mid + 1, r, L, R);
pushup(y);
pushup(tr);
}
例题
思路：将 \([x, y]\) 分裂出来。
-
将 \(t\) 树合并入 \(p\) 树：单次合并即可。
-
\(p\) 树种插入 \(x\) 个 \(q\)：单点修改。
-
查询 \([x, y]\) 中数的个数：区间求和。
-
查询第 \(k\) 小。
#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
typedef long long LL;
const int N = 2e5 + 10, M = N * 48;
int root[N], ls[M], rs[M], tot, tt = 1;
LL sum[M];
int n, m, a[N];
void pushup(int tr) {
sum[tr] = sum[ls[tr]] + sum[rs[tr]];
}
void split(int &tr, int &y, int l, int r, int L, int R) {
if (!tr) return y = 0, void();
if (L <= l && r <= R) return y = tr, tr = 0, void();
y = ++ tot;
if (L <= mid) split(ls[tr], ls[y], l, mid, L, R);
if (R > mid) split(rs[tr], rs[y], mid + 1, r, L, R);
pushup(y);
pushup(tr);
}
void update(int &tr, int l, int r, int u, int v) {
if (!tr) tr = ++ tot;
sum[tr] += v;
if (l == r) return;
if (u <= mid) update(ls[tr], l, mid, u, v);
else update(rs[tr], mid + 1, r, u, v);
}
int merge(int x, int y, int l, int r) {
if (!x || !y) return x | y;
sum[x] += sum[y];
if (l == r) return x;
ls[x] = merge(ls[x], ls[y], l, mid);
rs[x] = merge(rs[x], rs[y], mid + 1, r);
return x;
}
LL query(int tr, int l, int r, int L, int R) {
if (L > r || R < l) return 0;
if (L <= l && r <= R) return sum[tr];
return query(ls[tr], l, mid, L, R) + query(rs[tr], mid + 1, r, L, R);
}
int getval(int tr, int l, int r, int k) {
if (!tr) return -1;
if (l == r) return l;
if (sum[ls[tr]] >= k && sum[ls[tr]]) return getval(ls[tr], l, mid, k);
else return getval(rs[tr], mid + 1, r, k - sum[ls[tr]]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i], update(root[1], 1, n, i, a[i]);
for (int i = 1; i <= m; i ++ ) {
int op;
cin >> op;
switch(op) {
case 0: {
int p, x, y;
cin >> p >> x >> y;
split(root[p], root[ ++ tt], 1, n, x, y);
break;
}
case 1: {
int p, t;
cin >> p >> t;
root[p] = merge(root[p], root[t], 1, n);
break;
}
case 2: {
int p, x, q;
cin >> p >> x >> q;
update(root[p], 1, n, q, x);
break;
}
case 3: {
int p, x, y;
cin >> p >> x >> y;
cout << query(root[p], 1, n, x, y) << endl;
break;
}
case 4: {
int p, k;
cin >> p >> k;
cout << getval(root[p], 1, n, k) << endl;
break;
}
}
}
return 0;
}