线段树
线段树时=是完全二叉树,原理啥的就不写了，看这张图片应该能回忆起。
题目:
ProblemE: 操作格子
Time Limit: 1 Memory Limit: 128 MB Submit 0 Solved 0
Description
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
Input
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
Output
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
Sample Input
4 3 1 2 3 4 2 1 3 1 4 3 3 1 4
Sample Output
6 3
HINT
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。
思路:线段树
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#define in(x) scanf("%d",&x)
#define out(x) printf("%d",x)
using namespace std;
typedef long long int ll;
const int maxn=1e5+5;
struct node{
int l,r,max;
ll sum;
}a[400010];
void build(int i,int l,int r)//建树 初始化
{
int mid=(l+r)>>1;
a[i].l=l,a[i].r=r;
a[i].max=0,a[i].sum=0;
if(l==r) return;//如果左右边距相等则不再构建
build(2*i,l,mid);//左孩子 范围为l到mid
build(2*i+1,mid+1,r);//右孩子 范围为mid+1到r
}
void insert(int i,int v,int value)//往下延申更新sum和max
{
a[i].sum+=value;//延申经过的点都加上这个值
if(a[i].max<value) a[i].max=value;//更新最大值
if(a[i].l==a[i].r) return;//左右边距相等时,不再往下延申()
int mid=(a[i].l+a[i].r)>>1;
if(v<=mid){//插入到左孩子
insert(2*i,v,value);
}
else insert(2*i+1,v,value);//插入到右孩子
}
void update(int i,int v,int value)//更改
{
if(v==a[i].l&&v==a[i].r){//如果左右边距都对应相等
a[i].sum=value; // 则找到了对应的value
a[i].max=value;
return;
}
int mid=(a[i].l+a[i].r)>>1;
if(v<=mid){
update(2*i,v,value);//从左孩子出寻找
}
else update(2*i+1,v,value);//从右孩子中寻找
a[i].sum=a[2*i].sum+a[2*i+1].sum;//更新区间和
a[i].max=max(a[2*i].max,a[2*i+1].max);//搜索自上而下,更新自下而上
}
ll getsum(int i,int l,int r)//求区间和
{
if(l==a[i].l&&r==a[i].r) return a[i].sum;//如果左右边距都对应相等,
int mid=(a[i].l+a[i].r)>>1; // 则找到了对应的sum
if(r<=mid){
return getsum(2*i,l,r);//从左孩子出寻找
}
else if(l>mid){//从右孩子中寻找
return getsum(2*i+1,l,r);
}
else{
return getsum(2*i,l,mid)+getsum(2*i+1,mid+1,r);//左右均找
}
}
int getmax(int i,int l,int r)
{
if(l==a[i].l&&r==a[i].r) return a[i].max;//如果左右边距都对应相等,
int mid=(a[i].l+a[i].r)>>1; // 则找到了对应的max
if(r<=mid){
return getmax(2*i,l,r);//从左孩子出寻找
}
else if(l>mid){//从右孩子中寻找
return getmax(2*i+1,l,r);
}
else{
return max(getmax(2*i,l,mid),getmax(2*i+1,mid+1,r));//左右均找
}
}
int main()
{
int n,m,value,a,b,c;
in(n),in(m);
build(1,1,n);//每次从1开始往下延申
for(int i=1;i<=n;i++){
in(value);
insert(1,i,value);//每次依旧是从顶(1)往下延申
}
while(m--){
in(a),in(b),in(c);
if(a==1) update(1,b,c);
else if(a==2) printf("%lld\n",getsum(1,b,c));
else if(a==3) printf("%d\n",getmax(1,b,c));
}
}