请编写程序对数组a1?,a2?,...,an?进行如下操作 ：
1 i x：给定i,x，将ai? 加上x ；
2 l r：给定l,r，求al?+al+1?+...+ar?的值。
输入格式:
第一行包含2个正整数n和q，表示数组长度和查询个数。保证1≤n,q≤106。 第二行n个整数a1?,a2?,...,an?，表示初始数组。保证∣ai?∣≤106。 接下来q行，每行为一个操作。 保证 1≤l≤r≤n,∣x∣≤106。
输出格式:
对于每个 2 l r 操作输出一行，每行有一个整数，表示所求的结果。
输入样例:
3 2
1 2 3
1 2 0
2 1 3
输出样例:
6暴力解法是肯定拿不了全部分数的，从网上查了查原来又是线段树的算法结构。我看网上讲的都挺全乎的所以我在这里主要说说我碰到的问题。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll tree[600001];
void lotree(ll a[],ll index,ll start,ll end){
if(start==end){
tree[index]=a[start];
return ;
}
ll leftnode=2*index+1;
ll rightnode=2*index+2;
ll mid=(start+end)/2;
lotree(a,leftnode,start,mid);
lotree(a,rightnode,mid+1,end);
tree[index]=tree[leftnode]+tree[rightnode];
return ;
}
void updata(ll index,ll start,ll end,ll value,ll location){
if(start==end){
tree[index]=value;
return ;
}
ll leftnode=2*index+1;
ll rightnode=2*index+2;
ll mid=(start+end)/2;
if(start<=location&&location<=mid){//一定注意是location<=mid
updata(leftnode,start,mid,value,location);
}
else{
updata(rightnode,mid+1,end,value,location);
}
tree[index]=tree[leftnode]+tree[rightnode];
}
ll getsum(int index,int l,int r,int start,int end){
if(r<start||l>end){
return 0;
}
if(start>=l&&end<=r){
return tree[index];
}
ll leftnode=2*index+1;
ll rightnode=2*index+2;
ll mid=(start+end)/2;
ll leftsum=getsum(leftnode,l,r,start,mid);
ll rightsum=getsum(rightnode,l,r,mid+1,end);
return leftsum+rightsum;
}
int main(){
ll n,m;
ll i;
scanf("%lld%lld",&n,&m);
ll a[n];
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
lotree(a,0,0,n-1);
ll panduan,location;
for(i=0;i<m;i++){
scanf("%lld%lld",&panduan,&location);
switch(panduan){
case 1:{
ll value;
scanf("%lld",&value);
a[location-1]+=value;
updata(0,0,n-1,a[location-1],location-1);
break;
}
case 2:{
ll limit;
scanf("%lld",&limit);
ll result=getsum(0,location-1,limit-1,0,n-1);
printf("%lld\n",result);
}
}
}
system("pause");
}getsum里面的?注释地方还有就是；case2里面的location一定要-1，也就是跟你线段树组里面的数据对应，这样才能算出来结果，limit也是。
?