线段树模板
#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
