线段树

线段树1（区间加k，区间求和）

#include<bits/stdc++.h>
#define mid (((l)+(r))/2)
#define int long long
using namespace std;
const int N=100005;
int n,m;
int a[N],tree[N*4],b[N*4]; // tree: 区间和； b: 懒标记（延迟的加值）

inline void pushup(int p){ 
	// 向上更新节点 p 的值 = 左右子节点的和
	tree[p]=tree[p*2]+tree[p*2+1];
}

inline void pushdown(int l,int r,int p){
	// 将当前节点的懒标记向下传递
	b[p*2]+=b[p]; // 左子节点继承懒标记
	b[p*2+1]+=b[p];
	tree[p*2]+=b[p]*(mid-l+1); // 左区间加上懒标记贡献
	tree[p*2+1]+=b[p]*(r-mid); // 右区间同理
	b[p]=0; // 清空本节点懒标记
}

void build(int l,int r,int p){
	// 递归建树，将输入数组 a 构造成区间和线段树
	if(l==r){
		tree[p]=a[l];
		return;
	}
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	pushup(p);
}

void modify(int s,int t,int l,int r,int p,int x){
	// 区间 [s,t] 内每个元素加上 x
	if(s<=l&&r<=t){
		tree[p]+=x*(r-l+1); // 当前节点区间整体加上对应和
		b[p]+=x;            // 懒标记记录延迟加
		return;
	}
	pushdown(l,r,p); // 向下传懒标记，确保子节点正确
	if(s<=mid)modify(s,t,l,mid,p*2,x);
	if(t>=mid+1)modify(s,t,mid+1,r,p*2+1,x);
	pushup(p); // 修改完维护向上求和
}

int query(int s,int t,int l,int r,int p){
	// 查询区间 [s,t] 的区间和
	if(s<=l&&r<=t){
		return tree[p];
	}
	pushdown(l,r,p);
	int ret=0;
	if(s<=mid)ret+=query(s,t,l,mid,p*2);
	if(t>=mid+1)ret+=query(s,t,mid+1,r,p*2+1);
	pushup(p);
	return ret;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	while(m--){
		int opt;
		cin>>opt;
		if(opt==1){
			// 操作1：区间加
			int x,y,k;
			cin>>x>>y>>k;
			modify(x,y,1,n,1,k);
		}else{
			// 操作2：查询和
			int x,y;
			cin>>x>>y;
			cout<<query(x,y,1,n,1)<<endl;
		}
	}
	return 0;
}

---

线段树2（区间乘x、加x、求和）

#include <iostream>
using namespace std;
typedef long long ll;
ll n,mod,a[100005], d[270000],bx[270000], b[270000];
// d：节点区间和
// bx：乘法懒标（延迟乘）
// b：加法懒标（延迟加）
// 所有操作均取模 mod

ll wplus(ll a,ll b) {
	return (a+b)%mod;
}
ll wmul(ll a,ll b) {
	return (a*b)%mod;
}

void build(ll l,ll r,ll p) {
	// 建树，初始化加法懒标为0，乘法懒标为1
	b[p]=0;
	bx[p]=1;
	if(l==r) {
		d[p]=a[l];
		return;
	}
	ll m=(l+r)/2;
	build(l,m,p*2);
	build(m+1,r,p*2+1);
	d[p]=wplus(d[p*2],d[p*2+1]);
}

void lazytag(ll s,ll t,ll p) {
	// 下传懒标记
	ll m=(s+t)/2;
	// 将 p 的乘法、加法懒标作用到左右子节点
	
	// 左右子区间的值更新： d= d*乘标 + 加标*区间长度
	d[p*2]=wplus(d[p*2]*bx[p],b[p]*(m-s+1));
	d[p*2+1]=wplus(d[p*2+1]*bx[p],b[p]*(t-m));
		
	// 子节点的懒标记更新（复合操作）
	bx[p*2]=wmul(bx[p*2],bx[p]);
	bx[p*2+1]=wmul(bx[p*2+1],bx[p]);
	b[p*2]=wplus(b[p*2]*bx[p],b[p]);
	b[p*2+1]=wplus(b[p*2+1]*bx[p],b[p]);	
	
	// 清空当前节点懒标
	b[p]=0;
	bx[p]=1;
}

void update_add(ll l,ll r,ll c,ll s,ll t,ll p) {
	// 区间 [l,r] 加上 c
	if(l<=s&&t<=r) {
		b[p]=wplus(b[p],c);           // 累积加懒标
		d[p]=wplus(d[p],(t-s+1)*c);   // 更新当前节点的区间和
		return;
	}
	ll m=(s+t)/2;
	lazytag(s,t,p);
	if(l<=m)update_add(l,r,c,s,m,p*2);
	if(r>m)update_add(l,r,c,m+1,t,p*2+1);
	d[p]=wplus(d[p*2],d[p*2+1]);
}

void update_mul(ll l,ll r,ll c,ll s,ll t,ll p) {
	// 区间 [l,r] 乘以 c
	if(l<=s&&t<=r) {
		bx[p]=wmul(bx[p],c); // 更新乘懒标
		b[p]=wmul(b[p],c);   // 加懒标也要乘
		d[p]=wmul(d[p],c);   // 区间和乘 c
		return;
	}
	ll m=(s+t)/2;
	lazytag(s,t,p);
	if(l<=m)update_mul(l,r,c,s,m,p*2);
	if(r>m)update_mul(l,r,c,m+1,t,p*2+1);
	d[p]=wplus(d[p*2],d[p*2+1]);
}

ll getsum(ll l,ll r,ll s,ll t,ll p) {
	// 查询区间 [l,r] 的和
	if (l<=s&&t<=r)return d[p];
	ll m=(s+t)/2;
	lazytag(s,t,p);
	ll sum=0;
	if(l<=m)sum+=getsum(l,r,s,m,p*2)%mod;
	if(r>m)sum+=getsum(l,r,m+1,t,p*2+1)%mod;
	return sum%mod;
}

int main() {
	ll q,i1,i2,i3,i4;
	cin>>n>>q>>mod;
	for(ll i=1; i<=n; i++)cin>>a[i];
	build(1,n,1);
	while(q--) {
		cin>>i1>>i2>>i3;
		if (i1==3)
			// 查询区间和
			cout<<getsum(i2,i3,1,n,1)<<endl;
		else if(i1==2)
			// 区间加
			cin>>i4,update_add(i2,i3,i4,1,n,1);
		else 
			// 区间乘
			cin>>i4,update_mul(i2,i3,i4,1,n,1);
	}
	return 0;
}

---

可持久化线段树1（单点修改、单点查询）

#define N 1000005
int n,m,a[N];
struct node{
	int l;int r;  // 当前结点维护的区间边界
	int ls;int rs; // 左右子节点下标
	int v;         // 当前区间的值（这里是单点）
};
node tree[N*40];  // 每个修改都会生成新的节点副本（最多 N*logN 规模）
int cnt=0;

int build(int l,int r){
	// 建初始版本的线段树
	int p=cnt++;
	if(l==r){
		tree[p].v=a[l];
		return p;
	}
	int mid=(l+r)/2;
	tree[p].ls=build(l,mid);
	tree[p].rs=build(mid+1,r);
	return p; // 每个节点返回自身编号
}

int modify(int l,int r,int p,int x,int v){
	// 在旧版本 p 的基础上创建新版本，修改下标 x 的值为 v
	int q=cnt++;
	tree[q]=tree[p]; // 拷贝原节点信息
	if(l==r){
		tree[q].v=v; // 到达叶节点，更新值
		return q;
	}
	int mid=(l+r)/2;
	if(x<=mid){
		tree[q].ls=modify(l,mid,tree[p].ls,x,v);
	}
	else tree[q].rs=modify(mid+1,r,tree[p].rs,x,v);
	return q;
}

int query(int l,int r,int p,int x){
	// 在版本 p 中查询下标 x 的值
	if(l==r)return tree[p].v;
	int mid=(l+r)/2;
	if(x<=mid)	return query(l,mid,tree[p].ls,x);
	else		return query(mid+1,r,tree[p].rs,x);
}

int root[N]; // 各个版本的根节点下标

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=read(); // 假设存在 read()
	}
	root[0]=build(1,n); // 初始版本 0
	for(int i=1;i<=m;i++){
		int v=read();int opt=read();
		if(opt==1){
			// 基于版本 v 新建一个版本
			int loc=read();int val=read();
			root[i]=modify(1,n,root[v],loc,val);
		}else{
			// 查询版本 v
			int loc=read();
			cout<<query(1,n,root[v],loc)<<endl;
			root[i]=root[v]; // 查询不新建，有相同版本拷贝
		}
	}
	return 0;
}

---

可持久化线段树2（静态第k小查询）

#define N 500005
int n,q;
int a[N],t[N];
struct node {
	int l;  // 区间左边界
	int r;  // 区间右边界
	int ls; // 左子节点下标
	int rs; // 右子节点下标
	int cnt; // 当前区间内数值出现次数
};
node tree[N*40];
int root[N]; // 每个前缀版本的根
int cnt=0;

void pushup(int p){
	// 维护父节点计数 = 左右孩子计数之和
	tree[p].cnt=tree[tree[p].ls].cnt+tree[tree[p].rs].cnt; 
}

int build(int l,int r) {
	// 建立权值线段树（空树，所有计数为0）
	int p=cnt++;tree[p].cnt=0;
	tree[p].l=l,tree[p].r=r;
	if(l==r)return p;
	int mid=(l+r)/2;
	tree[p].ls=build(l,mid);
	tree[p].rs=build(mid+1,r);
	return p;
}

int modify(int l,int r,int p,int v) {
	// 基于旧版本 p，插入一个值 v（权值为 v 的点计数+1）
	int q=cnt++;
	tree[q]=tree[p];
	if(l==r){
		tree[q].cnt++;
		return q;
	}
	int mid=(l+r)/2;
	if(v<=mid){
		tree[q].ls=modify(l,mid,tree[p].ls,v);
	}else{
		tree[q].rs=modify(mid+1,r,tree[p].rs,v);
	}
	pushup(q);
	return q;
}

int query(int u,int v,int l,int r,int x){
	// 查询区间 [l,r] 内的第 x 小
	// 这里 u=右端根，v=左端-1根，差分计算出现次数
	if(l==r)return l;
	int mid=(l+r)/2;
	int tot=tree[tree[u].ls].cnt-tree[tree[v].ls].cnt;
	// 左子树内的元素个数 = tot
	if(tot>=x)	return query(tree[u].ls,tree[v].ls,l,mid,x);
	else		return query(tree[u].rs,tree[v].rs,mid+1,r,x-tot);
}

signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		t[i]=a[i];
	}
	sort(t+1,t+n+1);
	int m=unique(t+1,t+1+n)-t-1; // 离散化去重后长度
	root[0]=build(1,m);
	for(int i=1;i<=n;i++){
    	a[i]=lower_bound(t+1,t+1+m,a[i])-t; // 将值映射到离散坐标
    	root[i]=modify(1,m,root[i-1],a[i]);  // 建立前缀版本树
	} 
	while(q--){
		int l,r,k;
		cin>>l>>r>>k;
		int ans=query(root[r],root[l-1],1,m,k);
		cout<<t[ans]<<endl; // 反离散化输出
	}
	return 0;
}