动态开点是为了降低空间复杂度，防止爆内存，动态开点后空间复杂度为 $q\log{n}$，$q$ 为访问节点数。

对于维护区间长度 $n$ 已经确定的问题，实际上各个点对应的左右端点已经确定了，也可以完全不单独写 $build$ 函数创建线段树，以修改的方式初始化线段树。

以 P3372【模板】线段树 1 为例

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
	int ls,rs;
	long long lazy,sum;  //ls是线段树左儿子编号，rs是右儿子编号 
}t[N<<1];
int root=0,cnt=0;

void modify(int &p,int l,int r,int L,int R,int d) //注意由于要新开辟节点，p必须为引用类型 
{
	if(p==0)p=++cnt;  //当前节点如果不存在，新建立节点 
	
	if(L<=l&&r<=R)  //完全包含 
	{
		t[p].sum+=d*(r-l+1);
		t[p].lazy+=d;
		return;
	}
	int mid=l+r>>1;
	if(t[p].lazy)  //标记下传 
	{
		if(t[p].ls==0)t[p].ls=++cnt;
				
		t[t[p].ls].sum+=t[p].lazy*(mid-l+1);
		t[t[p].ls].lazy+=t[p].lazy;
		
		if(t[p].rs==0)t[p].rs=++cnt;
		
		t[t[p].rs].sum+=t[p].lazy*(r-mid);
		t[t[p].rs].lazy+=t[p].lazy;
		
		t[p].lazy=0;
	}	
	if(L<=mid)modify(t[p].ls,l,mid,L,R,d);
	if(mid<R)modify (t[p].rs,mid+1,r,L,R,d);
	
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
long long query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
		return t[p].sum;
		
	int mid=l+r>>1;
	if(t[p].lazy)     //下传标记 
	{
		if(t[p].ls==0)t[p].ls=++cnt;
		t[t[p].ls].sum+=t[p].lazy*(mid-l+1);
		t[t[p].ls].lazy+=t[p].lazy;
		if(t[p].rs==0)t[p].rs=++cnt;
		t[t[p].rs].sum+=t[p].lazy*(r-mid);
		t[t[p].rs].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
	long long ans=0;
	if(L<=mid)ans+=query(t[p].ls,l,mid,L,R);
	if(mid<R)ans+=query(t[p].rs,mid+1,r,L,R);
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int temp;
		cin>>temp;
		modify(root,1,n,i,i,temp);
	} 
	while(m--)
	{
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1)
		{
			cin>>k;
			modify(root,1,n,x,y,k);
		}
		else if(op==2)
			cout<<query(root,1,n,x,y)<<endl;
	} 

	return 0;
}

---

与树状数组类似，权值线段树能代替平衡树做一些求第 $k$ 大、排名、找前驱后继的操作。

以例题 P3369【模板】普通平衡树 为例：

写一个数据结构完成以下操作：

·1.插入 $x$

·2.删除 $x$

·3.查询 $x$ 的排名

·4.查询排名是 $x$ 的数

·5.求 $x$ 的前驱

·6.求 $x$ 的后继

这个是平衡树的模板题，平衡树的方法题解已经有很多了，下面介绍利用权值线段树动态开点解决此问题。

权值线段树就是在对应数值 $x$ 位置 $+1$ 表示在 $x$ 位置插入一个数 $x$，在对应数值 $x$ 位置 $-1$ 表示删除一个数 $x$ ,整个维护区间长度是 $x$ 的取值范围 $[-10^7,10^7]$ ,给整体区间平移 $10^7$，这样维护区间就是正数。但是区间长度太大，如果静态开点，显然空间不够用，这就需要动态开点，即当需要开点时再开点，空间复杂度为 $O(n\log(\max(x)))$。

上述6种操作，转化为以下三个核心函数：

1. 单点修改

void modify(int &p,int l,int r,int x,int d)
{
	if(!p)p=++cnt;
	if(l==r){
		t[p].sum+=d;return;
	 } 
	int mid= l+r>>1;
	if(x<=mid)modify(t[p].lson,l,mid,x,d);
	else modify(t[p].rson,mid+1,r,x,d);
	t[p].sum+=d;
}

插入$x$： 将$x$整体平移后，在$x$处$+1$

删除$x$： 将$x$整体平移后，在$x$处$-1$

2.区间查询：查询$[x,y]$的区间

int query(int p,int l,int r,int x,int y)  //查询区间x-y区间和
{
	if(!p)return 0;
	if(x<=l&&r<=y)return t[p].sum;
	int mid=l+r>>1;
	int ret=0;
	if(x<=mid)ret+=query(t[p].lson,l,mid,x,y);
	if(mid<y)ret+=query(t[p].rson,mid+1,r,x,y);
	return ret; 
} 

区间$[1,x]$的区间和，就是小于等于$x$个数

查询$x$的排名： 就是查询区间$[1,x-1]$的区间和，然后再加$1$

3.查询排名为 $x$ 的数（原始的值）

int query_num(int p,int l,int r,int x)  //从小到大 查询排名为x的数 
{
	if(!p)return 2e9;
	if(l==r)return l;
	int mid=l+r>>1;
	if(t[t[p].lson].sum>=x)return query_num(t[p].lson,l,mid,x);
	else return query_num(t[p].rson,mid+1,r,x-t[t[p].lson].sum);
}

查询排名是 $x$ 的数： 查询到位置后需要减去平移量

查询 $x$ 的前驱： 查询 $[1,x-1]$ 的数量，然后再查询这个数量对应的原始值

查询 $x$ 的后继： 查询 $[1,x]$ 的数量，然后再查询这个数量 $+1$ 对应的原始值

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int plu=1e7+10;   // 整体平移量
struct node{
	int sum,lson,rson;
}t[5000010];
int cnt,n,root;
void modify(int &p,int l,int r,int x,int d)
{
	if(!p)p=++cnt;
	if(l==r){
		t[p].sum+=d;return;
	 } 
	int mid= l+r>>1;
	if(x<=mid)modify(t[p].lson,l,mid,x,d);
	else modify(t[p].rson,mid+1,r,x,d);
	t[p].sum+=d;
}
int query(int p,int l,int r,int x,int y)  //查询区间x-y区间和
{
	if(!p)return 0;
	if(x<=l&&r<=y)return t[p].sum;
	int mid=l+r>>1;
	int ret=0;
	if(x<=mid)ret+=query(t[p].lson,l,mid,x,y);
	if(mid<y)ret+=query(t[p].rson,mid+1,r,x,y);
	return ret; 
} 
int query_num(int p,int l,int r,int x)  //从小到大 查询排名为x的数 
{
	if(!p)return 2e9;
	if(l==r)return l;
	int mid=l+r>>1;
	if(t[t[p].lson].sum>=x)return query_num(t[p].lson,l,mid,x);
	else return query_num(t[p].rson,mid+1,r,x-t[t[p].lson].sum);
}
int main()
{
	scanf("%d",&n);
	int opt,x;
	while(n--)
	{
		scanf("%d%d",&opt,&x);
		x+=plu;  //使其平移为正数
		int ans,xx; 
		switch(opt)
		{
			case 1:
				modify(root,1,2*plu,x,1);  break;
			case 2:
				modify(root,1,2*plu,x,-1);  break;
			case 3:
				ans=query(root,1,2*plu,1,x-1)+1;
				printf("%d\n",ans);
				break;
			case 4:
				ans=query_num(root,1,2*plu,x-plu)-plu;  //x平移后需要还原 
				printf("%d\n",ans);
				break;
			case 5:
				xx=query(root,1,2*plu,1,x-1);
				ans=query_num(root,1,2*plu,xx)-plu;
				printf("%d\n",ans);
				break;
			case 6:
				xx=query(root,1,2*plu,1,x);
				ans=query_num(root,1,2*plu,xx+1)-plu;
				printf("%d\n",ans);
				break;				 
		}
	}

	return 0;
}

---

学习完毕

{{ select(1) }}

• YES
• NO