线段树合并,听起来很高端,其实就是把两棵线段树相加。
引用一下一位大佬的图:
具体地说,每次合并操作我们考虑将 \(o_2\) 这棵树的信息加到 \(o_1\) 上,那么我们就遍历二者区间。
- 对于 \(o_1\) 没有但 \(o_2\) 有信息的区间,直接将 \(o_2\) 树上的节点接过来以节省时间。
- 对于二者都有的区间,我们选择遍历到叶子节点,然后信息依次递推回去。
- 对于 \(o_1\) 有但 \(o_2\) 没有信息的区间,不用动他。
可以发现,这个合并思路跟 \(FHQ-Treap\) 有异曲同工之妙,所以二者写法也有些相似之处。
上一道例题: 洛谷P3605
/*2022.11.27 洛谷AC
该代码目标:对于树上每个点,求其子树中有多少个权值比他大的点。
利用权值线段树,从下往上建树,将左右子树的线段树合并,然后直接查询即可。
*/
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n;
struct Ability{
int w;
int id;
bool cmp(Ability a, Ability b){
return a.w < a.w;
}
} A[N];
bool cmp(Ability a, Ability b){
return a.w < b.w;
}
int p[N];
map <int, int> g;
struct node{
int u, v, next;
} t[N << 1];
int head[N];
int bian = 0;
inline void addedge(int u, int v){
t[++bian] = (node){u, v, head[u]}, head[u] = bian;
return ;
}
int root[N];
int tot = 0;
int ans[N];
struct Segment_tree{
struct node{
int w;
int lson, rson;
} t[N << 2];
inline void pushup(int o){
t[o].w = t[t[o].lson].w + t[t[o].rson].w;
return ;
}
void insert(int &o, int l, int r, int x, int k){
if(!o) o = ++tot;
if(l == r && l == x){
t[o].w += k;
return ;
}
int mid = l + r >> 1;
if(mid >= x) insert(t[o].lson, l, mid, x, k);
else insert(t[o].rson, mid + 1, r, x, k);
pushup(o);
return ;
}
int query(int &o, int l, int r, int in, int end){
if(!o) o = ++tot;
if(l >= in && r <= end) return t[o].w;
if(l > end || r < in) return 0;
int mid = l + r >> 1;
int sum = 0;
if(mid >= in) sum += query(t[o].lson, l, mid, in, end);
if(mid < end) sum += query(t[o].rson, mid + 1, r, in, end);
return sum;
}
int merge(int o1, int o2, int l, int r){ // 跟 FHQ-Treap 一样的
if(!o1 || !o2) return o1 + o2; // 有一侧没有的话,直接把下面的接上去,省去了重复计算
if(l == r){
t[o1].w += t[o2].w;
return o1;
}
int mid = l + r >> 1;
t[o1].lson = merge(t[o1].lson, t[o2].lson, l, mid);
t[o1].rson = merge(t[o1].rson, t[o2].rson, mid + 1, r);
pushup(o1);
return o1;
}
} tree;
void dfs(int u){
tree.insert(root[u], 1, n, p[u], 1); // 这里写 n 是因为最多只有 n 种不同的权值,一般性地应该写权值中的最大值
for(int i = head[u]; i; i = t[i].next){
int v = t[i].v;
dfs(v);
root[u] = tree.merge(root[u], root[v], 1, n);
}
ans[u] = tree.query(root[u], 1, n, p[u] + 1, n);
return ;
}
int main(){
// freopen("hh.txt", "r", stdin);
read(n);
for(int i = 1; i <= n; i++){
read(A[i].w);
A[i].id = i;
}
sort(A + 1, A + n + 1, cmp);
int id = 0;
for(int i = 1; i <= n; i++){
if(!g[A[i].w]) g[A[i].w] = ++id;
}
for(int i = 1; i <= n; i++)
p[A[i].id] = g[A[i].w]; // 离散化操作,可以忽略
for(int i = 2; i <= n; i++){
int x; read(x);
addedge(x, i);
}
dfs(1);
for(int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}
标签:return,int,线段,mid,算法,思路,o2,o1
From: https://www.cnblogs.com/wondering-world/p/16929832.html