线段树合并算法思路

线段树合并，听起来很高端，其实就是把两棵线段树相加。

引用一下一位大佬的图：

具体地说，每次合并操作我们考虑将 \(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;
}