【poj 3468】A Simple Problemwith Integersベースラインツリーorツリー配列

以前のブログでは線分樹をあまり書いたことがないと言いました.今から補充します.
ACコードは以下の通りです(最初は負数読込最適化スラグWAを何発か見ていませんでした...本当に無言です):

<span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<cstring>
#define N 500005
#define ll long long

int n,m,icr[N],c[N][2]; ll sum[N];
int read(){
	int x=0,tmp=1; char ch=getchar();
	while (ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
	if (ch=='-'){ tmp=-1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x*tmp;
}
void pushdown(int k){
	if (icr[k]){
		int l=c[k][0],r=c[k][1],mid=(l+r)>>1;
		icr[k<<1]+=icr[k]; icr[k<<1|1]+=icr[k];
		sum[k<<1]+=(ll)icr[k]*(mid-l+1); sum[k<<1|1]+=(ll)icr[k]*(r-mid);
		icr[k]=0;
	}
}
void build(int k,int x,int y){
	c[k][0]=x; c[k][1]=y; icr[k]=0;
	if (x==y){ sum[k]=read(); return; } else{
		int mid=(x+y)>>1;
		build(k<<1,x,mid); build(k<<1|1,mid+1,y);
		sum[k]=sum[k<<1]+sum[k<<1|1];
	}
}
void ins(int k,int x,int y,int v){
	int l=c[k][0],r=c[k][1],mid=(l+r)>>1;
	if (x==l && y==r){
		icr[k]+=v; sum[k]+=(ll)v*(r-l+1); return;
	}
	pushdown(k);
	if (y<=mid) ins(k<<1,x,y,v); else
	if (x>mid) ins(k<<1|1,x,y,v); else{
		ins(k<<1,x,mid,v); ins(k<<1|1,mid+1,y,v);
	}
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
ll qry(int k,int x,int y){
	int l=c[k][0],r=c[k][1],mid=(l+r)>>1;
	if (x==l && y==r) return sum[k];
	pushdown(k);
	if (y<=mid) return qry(k<<1,x,y); else
	if (x>mid) return qry(k<<1|1,x,y); else{
		ll tmp=qry(k<<1,x,mid); tmp+=qry(k<<1|1,mid+1,y);
		return tmp;
	}
}
int main(){
	while (~scanf("%d%d",&n,&m)){
		build(1,1,n); int i; char ch;
		for (i=1; i<=m; i++){
			ch=getchar(); while (ch!='Q' && ch!='C') ch=getchar();
			if (ch=='C'){
				int x=read(),y=read(),v=read(); ins(1,x,y,v);
			} else{ int x=read(),y=read(); printf("%I64d
",qry(1,x,y)); }
		}
	}
	return 0;
}</span>

by lych
2016.1.8
-----------------------------------------------------------------------------------------------
後で木の配列の書き方があることに気づいて、1発補った(後で木の配列を書いたに違いない1 kコード).
区間修正単一点クエリはツリー配列で完了できることを知っています.元の配列がaであると仮定し,補助配列,例えばbを用いてa[i]をb[1]+b[2]+...+に変換する.b[i],すなわちa配列がb配列の接頭辞和に相当し,単点を接頭辞和に変換すると,区間修正(x,y)にzが加算され,b[x]+=z,b[y+1]-=zであれば,単純な推理ではa[i]=b[1]+b[2]+...b[i].そこで、メンテナンス接頭辞の和を単一の変更に変換します.区間クエリを行う場合は、接頭辞和の接頭辞和を維持することに相当します.これはbzojにこのような問題があります.具体的には忘れています.
実際、c[i]=a[1]+a[2]+...a[i]=b[1]*i+b[2]*(i-1)+...+b[i]*1=b[1]*n+b[2]*(n-1)+...+b[i]*(n-i+1)-(b[1]+b[2]+...+b[n]*(n-i)つまり、b配列の接頭辞と、b[1]*n,b[2]*(n-1)のような形を維持し、b[n]*1の配列の接頭辞和は二重接頭辞和を得ることができる.ツリー配列を利用すればよい.
MACコードは以下の通りである.

<span style="font-size:18px;">#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 100005
using namespace std;

int n,m; ll c[2][N];
int read(){
	int x=0,tmp=1; char ch=getchar();
	while (ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
	if (ch=='-'){ tmp=-1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x*tmp;
}
void ins(int k,int x,ll t){
	int i; for (i=x; i<=n; i+=i&(-i)) c[k][i]+=t;
}
ll qry(int k,int x){
	ll sum=0,i; for (i=x; i; i-=i&(-i)) sum+=c[k][i]; return sum;
}
void mdy(int x,int y,ll t){
	ins(0,x,t); ins(0,y+1,-t);
	ins(1,x,t*(n-x+1)); ins(1,y+1,-t*(n-y));
}
int main(){
	while (~scanf("%d%d",&n,&m)){
		int i; char ch; memset(c,0,sizeof(c));
		for (i=1; i<=n; i++){
			int tmp=read(); mdy(i,i,(ll)tmp);
		}
		while (m--){
			ch=getchar(); while (ch!='Q' && ch!='C') ch=getchar();
			if (ch=='C'){
				int x=read(),y=read(),z=read(); mdy(x,y,(ll)z);
			} else{
				int x=read()-1,y=read();
				printf("%I64d
",qry(1,y)-qry(0,y)*(n-y)-qry(1,x)+qry(0,x)*(n-x));
			}
		}
	}
	return 0;
}
</span>

by lych
2016.1.9