线段树

线段树是一个基于分治思想的二叉树结构，同于再区间上进行信息统计，便于区间修改和区间求值的数据结构。

比如线段树可以：

• 求任意区间的最大值
• 求任意区间和
• 求区间连续最大和

线段树结构一般用数组就可以表示

struct node
{
	int l,r,data;//l,r分别表示当前节点表示的区间[l,r]，data表示这个区间的最大值，根据不同的问题可以不同的表示
}a[10000*4+10];

若 a[p] 表示当前的节点 a[p*2] 就是这个节点的左节点 a[p*2+1] 就是当前节点的右节点。

下面给出线段树模板：

#include<bits/stdc++.h>
using namespace std;
int k[10010],n,l,r,t,x,v;
string str;
struct node
{
	int l,r,data;
}a[10000*4+10];
void build(int p,int l,int r)
{
	a[p].l=l,a[p].r=r;
	if(l==r)
	{
		a[p].data=k[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	a[p].data=max(a[p*2].data,a[p*2+1].data);
}
void change(int p,int x,int v)//把p[x]改成v 
{
	if(a[p].l==a[p].r)
	{
		a[p].data=v;
		return ;
	}
	int mid=(a[p].l+a[p].r)>>1;
	if(x<=mid)	change(p*2,x,v);
	else change(p*2+1,x,v);
	a[p].data=max(a[p*2].data,a[p*2+1].data);
}
int ask(int p,int l,int r)//询问区间[l,r]的最大值
{
	if(l<=a[p].l&&r>=a[p].r)	return a[p].data;
	int mid=(a[p].l+a[p].r)>>1;
	int val=-0x3f3f3f3f;
	if(l<=mid)	val=max(ask(p*2,l,r),val);
	if(r>mid)	val=max(ask(p*2+1,l,r),val);
	return val;
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>k[i];
	build(1,1,n);
	cin>>t;
	while(t--)
	{
		cin>>str;
		if(str=="ask")
		{
			cin>>l>>r;
			cout<<ask(1,l,r)<<endl;
		}
		else if(str=="change")
		{
			cin>>x>>v;
			change(1,x,v);
		}
	}
	return 0;
}