线段树分裂与合并
参考: bilibili
分裂: 把一棵线段树进行拆分
合并: 把两棵线段树进行合并
可以利用线段树分裂合并解决区间拆分合并的问题
前置: 动态开点线段树
合并
图示->
把2个线段树合并到一起
void merge(int &x, int y)
{
if(!x || !y) x |= y;
else
{
t[x].val += t[y].val;
merge(t[x].l, t[y].l);
merge(t[x].r, t[y].r);
}
}
合并后->
分裂
分为按值分裂和按区间分裂
按区间分裂:
//l和r表示递归到的节点维护的区间为[l, r]
//k为当前节点编号(老线段树)
//x和y是把[x, y]这个区间抽出来
int split(int l, int r, int &k, int x, int y)
{
int p = ++ idx;
if(x <= l && y >= r)
{
t[p] = t[k];
k = 0;
}
else
{
int mid = l + r >> 1;
if(x <= mid)
t[p].l = split(l, mid, t[k].l, x, y);
if(y > m)
t[p].r = split(mid + 1, r, t[k].r, x, y);
pushup(k);
pushup(p);
}
return p;
}
把[2, 5]这个区间拿出来后->
注意
线段树合并分裂巨灵活, 所以不能只背模板
比如合并中if(!(x && y)) x |= y的写法
对于x为NULL, y不为NULL时, 会直接用y树的节点替换x树的NULL, 在后面的操作中可能会破坏y的结构, 在一些y树合并后仍有用途的题中是不可取的
空间复杂度
一般方案:
\(2 \times maxm \times logmaxn\)
\(maxm\)是最大询问次数, \(maxn\)为线段树最大大小
例题
P5494
本题中类似权值线段树, 存储的是每个数值出现了多少次
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
struct node
{
int l, r;
ll val;
}t[N * 40];
int idx, root[N];
int n, m;
void pushup(int p)
{
t[p].val = t[t[p].l].val + t[t[p].r].val;
}
void change(int l, int r, int &p, int x, int val)
{
if(!p) p = ++ idx;
t[p].val += val;
if(l == r) return;
int mid = l + r >> 1;
if(x <= mid) change(l, mid, t[p].l, x, val);
else change(mid + 1, r, t[p].r, x, val);
}
void merge(int &x, int y)
{
if(!x || !y) x |= y;
else
{
t[x].val += t[y].val;
merge(t[x].l, t[y].l);
merge(t[x].r, t[y].r);
}
}
int split(int l, int r, int &k, int x, int y)
{
int p = ++ idx;
if(x <= l && y >= r)
{
t[p] = t[k];
k = 0;
}
else
{
int mid = l + r >> 1;
if(x <= mid) t[p].l = split(l, mid, t[k].l, x, y);
if(y > mid) t[p].r = split(mid + 1, r, t[k].r, x, y);
pushup(p);
pushup(k);
}
return p;
}
ll query(int l, int r, int p, int x, int y)
{
if(x <= l && r <= y) return t[p].val;
int mid = l + r >> 1;
ll sum = 0;
if(x <= mid) sum += query(l, mid, t[p].l, x, y);
if(y > mid) sum += query(mid + 1, r, t[p].r, x, y);
return sum;
}
int query(int l, int r, int p, int kth)
{
if(l == r) return l;
int mid = l + r >> 1;
if(kth <= t[t[p].l].val) return query(l, mid, t[p].l, kth);
else return query(mid + 1, r, t[p].r, kth - t[t[p].l].val);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
change(1, n, root[1], i, x);
}
int last = 1;
while(m -- )
{
int op, p, t1, x, y, q, k;
scanf("%d%d", &op, &p);
switch (op)
{
case 0:
scanf("%d%d", &x, &y);
root[++ last] = split(1, n, root[p], x, y);
break;
case 1:
scanf("%d", &t1);
merge(root[p], root[t1]);
break;
case 2:
scanf("%d%d", &x, &q);
change(1, n, root[p], q, x);
break;
case 3:
scanf("%d%d", &x, &y);
cout << query(1, n, root[p], x, y) << endl;
break;
case 4:
scanf("%d", &k);
if(k > t[root[p]].val) cout << -1 << endl;
else cout << query(1, n, root[p], k) << endl;
break;
}
}
return 0;
}
P4556
要用树上差分
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[2 * N], ne[N * 2], idx;
int fa[N][18], d[N];
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs_for_father(int u, int father)
{
fa[u][0] = father, d[u] = d[father] + 1;
for(int i = 1; i < 18; i ++ )
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == father) continue;
dfs_for_father(j, u);
}
}
int lca(int x, int y)
{
if(d[x] > d[y]) swap(x, y);
for(int i = 17; i >= 0; i -- )
if(d[fa[y][i]] >= d[x])
y = fa[y][i];
if(x == y) return x;
for(int i = 17; i >= 0; i -- )
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
#define y second
#define x first
typedef pair<int, int> PII;
struct node
{
int l, r;
PII val;
}t[N * 70];
int cnt, root[N];
PII max(PII a, PII b)
{
if(a.x > b.x) return a;
else if(a.x == b.x)
{
if(a.y >= b.y) return b;
else return a;
}
else return b;
}
void pushup(int p)
{
t[p].val = max(t[t[p].l].val, t[t[p].r].val);
}
void change(int l, int r, int &p, int pos, int val)
{
if(!p) p = ++ cnt;
if(l == r)
{
t[p].val.x += val;
t[p].val.y = pos;
return;
}
int mid = l + r >> 1;
if(pos <= mid) change(l, mid, t[p].l, pos, val);
else change(mid + 1, r, t[p].r, pos, val);
pushup(p);
}
void merge(int &a, int b, int l = 1, int r = N)
{
if(!a || !b) a |= b;
else if(l == r)
t[a].val.x += t[b].val.x;
else
{
int mid = l + r >> 1;
merge(t[a].l, t[b].l, l, mid);
merge(t[a].r, t[b].r, mid + 1, r);
pushup(a);
}
}
#undef y
#undef x
int ans[N];
void dfs_for_answer(int u)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa[u][0]) continue;
dfs_for_answer(j);
merge(root[u], root[j]);
}
if(t[root[u]].val.first)
ans[u] = t[root[u]].val.second;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs_for_father(1, 0);
while(m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
change(1, N, root[a], c, 1);
change(1, N, root[b], c, 1);
change(1, N, root[lca(a, b)], c, -1);
change(1, N, root[fa[lca(a, b)][0]], c, -1);
}
dfs_for_answer(1);
for(int i = 1; i <= n; i ++ )
cout << ans[i] << endl;
return 0;
}