ツリー配列テンプレート

変更

void add(int loc,int value){
  for (int i=loc;i<=n;i+=i&(-i))
    c[i]+=value;
}

検索

int query(int loc){
  int ans=0;
  for (int i=loc;i>0;i-=i&(-i))
    ans+=c[i];
  return ans;
}

ツリー配列クエリー接頭辞和のため、区間修正ポイントクエリーまたはポイント修正区間クエリーのみを実現できます.
(昨日受講した先輩は区間最値を求めてもいいと言っていました)
ポイント修正区間クエリー(ポイント値、クエリー接頭辞、減算)

#include<iostream>
#include<cstring>
#include<cstdio>
int n,m,x,y,ty,ans,p,q;
int a[100005],c[100005];
using namespace std;
void add(int loc,int value){
	for (int i=loc;i<=n;i+=i&(-i))
	  c[i]+=value;
}
int query(int loc){
	int ans=0;
	for (int i=loc;i>0;i-=i&(-i))
	  ans+=c[i];
	return ans;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	for (int i=1;i<=n;++i)
	  add(i,a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;++i){
		scanf("%d%d%d",&ty,&x,&y);
		if (ty==1)
		  add(x,y);
		else if (ty==2){
			p=query(x-1);
			q=query(y);
			ans=q-p;
			printf("%d
",ans);
		}
	}
}

区間変更点クエリー(現在のポイントと前のポイントの差を格納し、変更時に区間[l,r]lに加算し、r+1を減算し、クエリーは依然として接頭辞和である)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,ty,a,b,x,ans;
int s[100005],c[100005];
void add(int loc,int value){
	for (int i=loc;i<=n;i+=i&(-i))
	  c[i]+=value;
}
int query(int loc){
	int ans=0;
	for (int i=loc;i>0;i-=i&(-i))
	  ans+=c[i];
	return ans;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	  scanf("%d",&s[i]);
	for (int i=1;i<=n;++i)
	  add(i,s[i]-s[i-1]);
	scanf("%d",&m);
	for (int i=1;i<=m;++i){
		scanf("%d%",&ty);
		if (ty==1){
			scanf("%d%d%d",&a,&b,&x);
			add(a,x);
			add(b+1,-x);
		}
		if (ty==2){
			scanf("%d",&x);
			ans=query(x);
			printf("%d
",ans);
		}
	}
}