rt,我的代码是由树状数组1的代码改改提交上去的
#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
long long int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int a[MAX*4];
struct a
{
int l,r,kind;
bool ye;
} tree[MAX*4];
void build(int n,int l,int r)
{
int mid=(l+r)/2;
tree[n].l=l;tree[n].r=r;
if(l==r)
{
tree[n].ye=true;
tree[n].kind=a[l];
return;
}else{
build(n*2,l,mid);
build(n*2+1,mid+1,r);
tree[n].kind=tree[n*2].kind+tree[n*2+1].kind;
}
}
void add(int x,int k,int now)
{
int mid=(tree[now].l+tree[now].r)/2;
if(tree[now].l==tree[now].r)
{
tree[now].kind+=k;
return;
}else{
if(x>mid) add(x,k,now*2+1);else
add(x,k,now*2);
tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
}
}
long long int find(int l,int r,int n)
{
int mid=(tree[n].l+tree[n].r)/2;
if(tree[n].l==l&&tree[n].r==r)
{
return tree[n].kind;
}
if( l > mid ) return find( l , r , n * 2 + 1 );
else if( mid >= r ) return find( l , r , n * 2 );
return find( l , mid , n * 2 ) + find( mid + 1 , r , n * 2 + 1 );
}
int main()
{
int n;
cin>>n;
int x;
cin>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=x;i++)
{
int a;
cin>>a;
if(a==1)
{
int x,k;
cin>>x>>k;
add(x,k,1);
}else{
int x,y;
cin>>x>>y;
cout<<find(x,y,1)<<endl;
}
}
return 0;
}
#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
long long int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int a[MAX*4];
struct a
{
int l,r,kind;
bool ye;
} tree[MAX*4];
void build(int n,int l,int r)
{
int mid=(l+r)/2;
tree[n].l=l;tree[n].r=r;
if(l==r)
{
tree[n].ye=true;
tree[n].kind=a[l];
return;
}else{
build(n*2,l,mid);
build(n*2+1,mid+1,r);
tree[n].kind=tree[n*2].kind+tree[n*2+1].kind;
}
}
void ac(int l,int r,int now,int k)
{
/*int mid=(tree[now].l+tree[now].r)/2;
if(tree[now].l==tree[now].r)
{
tree[now].kind+=k;
return;
}else{
if(x>mid) add(x,k,now*2+1);else
add(x,k,now*2);
tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
}*/
if(tree[tree[now].l].ye==1&&tree[tree[now].r].ye==1)
{
tree[tree[now].l].kind+=k;
tree[tree[now].r].kind+=k;
tree[now].kind=tree[tree[now].l].kind+tree[tree[now].r].kind;
return;
}else{
ac(l,tree[tree[now].l].r,tree[now].l,k);
ac(tree[tree[now].r].l,r,tree[now].r,k);
tree[now].kind=tree[tree[now].l].kind+tree[tree[now].r].kind;
}
}
// tree[now].kind+=k;
void add(int x,int y,int k,int now)
{
int mid=(tree[now].l+tree[now].r)/2;
if(tree[now].l==x&&tree[now].r==y)
{
// tree[now].kind+=k;
ac(x,y,now,k);
return;
}else{
if(x>mid) add(x,y,k,now*2+1);else
add(x,y,k,now*2);
tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
}
}
long long int find(int l,int r,int n)
{
int mid=(tree[n].l+tree[n].r)/2;
if(tree[n].l==l&&tree[n].r==r)
{
return tree[n].kind;
}
if( l > mid ) return find( l , r , n * 2 + 1 );
else if( mid >= r ) return find( l , r , n * 2 );
return find( l , mid , n * 2 ) + find( mid + 1 , r , n * 2 + 1 );
}
int main()
{
int n;
cin>>n;
int x;
cin>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=x;i++)
{
int a;
cin>>a;
if(a==1)
{
int x,y,k;
cin>>x>>y>>k;
add(x,y,k,1);
}else{
int x,y;
cin>>x>>y;
cout<<find(x,y,1)<<endl;
}
}
return 0;
}