线段树扩展

动态开点线段树

需要新开结点的时候去新开就完事了。不过结点x的左右儿子就不一定是2x和2x+1了，而是在结点中用ls和rs两个量来维护。

int n,cnt,root;
int sum[N*2],ls[N*2],rs[N*2];

void update(int& p,int s,int t,int x,int f){
	if(!p) p=++cmt;
	if(s==t){
		sum[p]+=f;
		return;
	}
	int m=(s+t)/2;
	if(x<=m) update(ls[p],s,m,x,f);
	else update(rs[p],m+1,t,x,f);
	sum[p]+=sum[ls[p]]+sum[rs[p]];
}

权值线段树

权值线段树维护的是区间内对应数字的某种值（如出现次数）。

操作：和线段树是一样的，维护区间和就行了。

作用：求出现次数、第k大、排名、前驱后继等平衡树能干的事情。

线段树合并

顾名思义，线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护树上或是图上的信息。

显然，我们不可能真的每次建满一颗新的线段树，因此我们需要使用动态开点线段树。

线段树合并的过程本质上相当暴力：

假设两颗线段树为 A 和 B，我们从 1 号节点开始递归合并。类似DFS的方式。

递归到某个节点时，如果 A 树或者 B 树上的对应节点为空，直接返回另一个树上对应节点，这里运用了动态开点线段树的特性。

如果递归到叶子节点，我们合并两棵树上的对应节点。

最后，根据子节点更新当前节点并且返回。

可以证明，将n个大小为1的线段树合并为1个大小为n的线段树的时间复杂度是O(nlogn)。

From OiWiki

int merge(int a,int b,int l,int r){
	if(!a) return b;
	if(!b) return a;
	if(l==r){
		// do something...
		return a;
	}
	int mid=(l+r)/2;
	tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
	tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
	pushup(a);
	return a;
}

板子

线段树合并板子题。

首先对于每次操作，利用树上差分来处理，即x[z]++,y[z]++,(lca(x,y))[z]--,fa(lca(x,y))[z]--。数组表示z在该结点出现了多少次。

那么求一个结点的某种颜色的出现次数就是把它为根的子树的所有对应数组求和，但是直接求和是O(mn)的，复杂度太高。

因此可以用线段树合并来优化。

具体来说，对每个结点建一棵权值线段树，树上结点表示[l,r]区间内的颜色出现了多少次。在所有操作完成后做一次DFS，把子结点的线段树合并到父结点上，时间复杂度O(mlogn)。

例题

给你一棵有n个结点的树，每个结点有一个编号为c的颜色，对每个结点x，求以x为根的子树中，出现次数最多的颜色的编号和（因为可能不止一种颜色的出现次数最多）。 n≤10^5。

也是板子，感觉比上一题简单。

这题只要dfs一下，将每个子节点的线段树与父亲节点线段树合并，再将父亲节点的颜色插入该节点对应的线段树，然后直接查询答案就可以了。

树上启发式合并

其实前两题有树上启发式合并的做法。这里也稍微讲一下。

树上启发式合并用于离线处理一些树上问题，通常是子树询问。

树上启发式合并的本质是链剖分，和树链剖分类似。

算法流程是将高度低的树合并为高度高的树的子树中，具体如下：

第一次 dfs，预处理每个点的父亲、子树大小、重儿子（通常是子树大小最大的儿子），类似树链剖分的第一次 dfs。

第二次 dfs，设当前到点x，先dfs x的所有轻儿子并删除，然后dfs x的所有重儿子并保留，接着将x本身和轻儿子的所有点加入，最后处理x的询问。

树上启发式合并的具体介绍可以参考

https://pzy.blog.luogu.org/dsu-on-tree-xue-xi-bi-ji

相当一部分线段树合并的题都可以用树上启发式合并来做。

主席树（可持久化权值线段树）

板子

模板

静态区间第k小（主席树）

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr int MAXN = 1e5;  // 数据范围
int tot, n, m;
int sum[(MAXN << 5) + 10], rt[MAXN + 10], ls[(MAXN << 5) + 10],
    rs[(MAXN << 5) + 10];
int a[MAXN + 10], ind[MAXN + 10], len;

int getid(const int &val) {  // 离散化
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r) {  // 建树
  int root = ++tot;
  if (l == r) return root;
  int mid = l + r >> 1;
  ls[root] = build(l, mid);
  rs[root] = build(mid + 1, r);
  return root;  // 返回该子树的根节点
}

int update(int k, int l, int r, int root) {  // 插入操作
  int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  int mid = l + r >> 1;
  if (k <= mid)
    ls[dir] = update(k, l, mid, ls[dir]);
  else
    rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}

int query(int u, int v, int l, int r, int k) {  // 查询操作
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // 通过区间减法得到左儿子中所存储的数值个数
  if (l == r) return l;
  if (k <= x)  // 若 k 小于等于 x ，则说明第 k 小的数字存储在在左儿子中
    return query(ls[u], ls[v], l, mid, k);
  else  // 否则说明在右儿子中
    return query(rs[u], rs[v], mid + 1, r, k - x);
}

void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  memcpy(ind, a, sizeof ind);
  sort(ind + 1, ind + n + 1);
  len = unique(ind + 1, ind + n + 1) - ind - 1;
  rt[0] = build(1, len);
  for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

int l, r, k;

void work() {
  while (m--) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]);  // 回答询问
  }
}

int main() {
  init();
  work();
  return 0;
}

线段树合并

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
#define M 6000005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
struct E{int v,nxt;}e[maxn<<1];
int l[M],r[M],d[M],t[M];
int top[maxn],fa[maxn],head[maxn],deep[maxn],son[maxn],sum[maxn],X[maxn],Y[maxn],Z[maxn],Ans[maxn];
int n,m,rt[maxn],cnt,R,num;
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
void dfs1(int x) {
    sum[x]=1;int maxx=-1;
    for(re int i=head[x];i;i=e[i].nxt)
    if(!deep[e[i].v])
    {
        deep[e[i].v]=deep[x]+1,fa[e[i].v]=x;
        dfs1(e[i].v);
        sum[x]+=sum[e[i].v];
        if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;
    }
}
void dfs2(int x,int topf) {
    top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(re int i=head[x];i;i=e[i].nxt) if(!top[e[i].v]) dfs2(e[i].v,e[i].v);
}
inline int LCA(int x,int y) {
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y]) return x;return y;
}
inline void pushup(int a) {
    if(d[l[a]]>=d[r[a]]) d[a]=d[l[a]],t[a]=t[l[a]];
        else d[a]=d[r[a]],t[a]=t[r[a]];
}
int change(int a,int x,int y,int pos,int val) {
    if(!a) a=++cnt;
    if(x==y) {d[a]+=val,t[a]=x;return a;}
    int mid=x+y>>1;
    if(pos<=mid) l[a]=change(l[a],x,mid,pos,val);
        else r[a]=change(r[a],mid+1,y,pos,val);
    pushup(a);
    return a;
}
int merge(int a,int b,int x,int y) {
    if(!a) return b;if(!b) return a;
    if(x==y) {d[a]+=d[b];t[a]=x;return a;}
    int mid=x+y>>1;
    l[a]=merge(l[a],l[b],x,mid),r[a]=merge(r[a],r[b],mid+1,y);
    pushup(a);return a;
}
void Redfs(int x) {
    for(re int i=head[x];i;i=e[i].nxt)
    if(deep[e[i].v]>deep[x]) Redfs(e[i].v),rt[x]=merge(rt[x],rt[e[i].v],1,R);
    if(d[rt[x]]) Ans[x]=t[rt[x]];
}
int main()
{
    n=read(),m=read();int x,y,z;
    for(re int i=1;i<n;i++) x=read(),y=read(),add(y,x),add(x,y);
    deep[1]=1,dfs1(1),dfs2(1,1);
    for(re int i=1;i<=m;i++) X[i]=read(),Y[i]=read(),Z[i]=read(),R=max(R,Z[i]);
    for(re int i=1;i<=m;i++)
    {
        int lca=LCA(X[i],Y[i]);
        rt[X[i]]=change(rt[X[i]],1,R,Z[i],1),rt[Y[i]]=change(rt[Y[i]],1,R,Z[i],1);
        rt[lca]=change(rt[lca],1,R,Z[i],-1);
        if(fa[lca]) rt[fa[lca]]=change(rt[fa[lca]],1,R,Z[i],-1);
    }
    Redfs(1);
    for(re int i=1;i<=n;i++) printf("%d\n",Ans[i]);
    return 0;
}