线段树模板(最简便)

Posted by yjjr's blog on February 6, 2018

线段树模板

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct node
{
	int a,b;//表示区间起始结束点
	int Max,Min,Sum;
}tree[maxn<<1];
int v,k;

void change(int p,int k,int v)
{
	if(tree[p].a==tree[p].b&&tree[p].a==k)
	{
		tree[p].Max=v; tree[p].Min=v; tree[p].Sum=v; return;
	}
	else 
	{
		int mid=(tree[p].a+tree[p].b)>>1;
		if(k<=mid)change(p*2,k,v);
		else change(p*2+1,k,v);
		tree[p].Min=min(tree[p*2].Min,tree[p*2+1].Min);
		tree[p].Max=max(tree[p*2].Max,tree[p*2+1].Max);
		tree[p].Sum=tree[p*2].Sum+tree[p*2+1].Sum;
	}
}
void build(int p,int l,int r)
{
	tree[p].a=l;tree[p].b=r;
	if(l==r)return;
	else
	{
		build(p*2,l,(l+r)/2);
		build(p*2+1,(l+r)/2+1,r);
	}
}//建立标记,并无实际操作

int queryMax(int p,int l,int r)
{
	if(tree[p].a==l&&tree[p].b==r)return tree[p].Max;
	int mid=(tree[p].a+tree[p].b)/2;
	if(mid>=r)return queryMax(p*2,l,r);
	if(mid<l)return queryMax(p*2+1,l,r);
	return max(queryMax(p*2,l,mid),queryMax(p*2+1,mid+1,r));
}
int queryMin(int p,int l,int r)
{
	if(tree[p].a==l&&tree[p].b==r)return tree[p].Min;
	int mid=(tree[p].a+tree[p].b)/2;
	if(mid>=r)return queryMin(p*2,l,r);
	if(mid<l)return queryMin(p*2+1,l,r);
	return min(queryMin(p*2,l,mid),queryMin(p*2+1,mid+1,r));
}
int querySum(int p,int l,int r)
{
	if(tree[p].a==l&&tree[p].b==r)return tree[p].Sum;
	int mid=(tree[p].a+tree[p].b)/2;
	if(mid>=r) return querySum(p*2,l,r);
	if(mid<l) return querySum(p*2+1,l,r);
	return (querySum(p*2,l,mid)+querySum(p*2+1,mid+1,r)); 
}
int main()
{
	int n=read(),m=read();
	build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		int x=read();
		change(1,i,x);
	}
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		cout<<queryMax(1,x,y)<<" "<<queryMin(1,x,y)<<" "<<querySum(1,x,y)<<endl;
	}
	return 0;
}




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr