参考链接：http://blog.****.net/dyx404514/article/details/8817717
写的很详细，这里就不再赘述，附上我的代码。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
/*
AC
http://blog.****.net/dyx404514/article/details/8817717
*/
using namespace std;
const int maxn=;
int n,m;
int nn; //最后离散后的点的个数
long long val[maxn*]; //存储所有数据
long long hashval[maxn*]; //存储离散后的数据
long long a[maxn],aa[maxn]; //存储初始序列
int pos[maxn]; //存储初始序列在hashval中的位置
int cnt=-; //用于离散时，统计总共有多少个数
int idx=; //用于建树时，获取初始的n个坐标值在hashval中位置的索引
struct Node{
int num; //该区间有多少个点。
long long sum; //该区间点的横坐标之和。
long long ans; //该区间每一对点的距离之和。
}tree[maxn<<]; struct Query{
int t,p,d;
long long l,r;
}q[maxn]; /*
注意：这里二分查找时，用mark标记是查找>=m的数的位置，还是查找<=m的数的位置。
当更新的时候，mark=2即可。
当查询时，查找l的时候，由于l可能不存在，所以我们查找的时候需要查找>=l的最近的数的位置，此时mark=1；
查找r的时候，由于r可能不存在，所以我们查找的时候需要查找<=r的最近的数的位置，此时mark=2
*/
int binarySearch(long long m,int mark,int length){
int l=,r=length+,mid;
while(r-l>){
mid=(l+r)>>;
if(hashval[mid]<=m)
l=mid;
else
r=mid;
}
if(hashval[l]==m)
return l;
if(mark==)
return l+;
else
return l;
} void pushUp(Node &rt,Node &ls,Node &rs){
rt.num=ls.num+rs.num;
rt.sum=ls.sum+rs.sum;
rt.ans=ls.num*rs.sum-rs.num*ls.sum+ls.ans+rs.ans; //公式的话，很容易就能推出，这里就不详细说了
}
void build(int rt,int L,int R){
if(L==R){
tree[rt].num=tree[rt].sum=tree[rt].ans=;
if(idx<=n && L==pos[idx]){
tree[rt].num=;
tree[rt].sum=aa[idx];
tree[rt].ans=;
idx++;
}
return;
}
int mid=(L+R)>>;
build(lson);
build(rson);
pushUp(tree[rt],tree[rt<<],tree[rt<<|]);
}
/*
op=1即是加入一个数
op=0即使去除一个数
*/
void update(int rt,int L,int R,int x,int op,int val){
if(L==R){
if(op==){
tree[rt].num=;
tree[rt].sum=val;
tree[rt].ans=;
}
else{
tree[rt].num=tree[rt].sum=tree[rt].ans=;
}
return;
}
int mid=(L+R)>>;
if(x<=mid)
update(lson,x,op,val);
else
update(rson,x,op,val);
pushUp(tree[rt],tree[rt<<],tree[rt<<|]);
}
Node query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r){
return tree[rt];
}
Node tmp,a,b;
int mid=(L+R)>>;
if(r<=mid)
tmp=query(lson,l,r);
else if(l>mid)
tmp=query(rson,l,r);
else{
a=query(lson,l,mid);
b=query(rson,mid+,r);
pushUp(tmp,a,b);
}
return tmp;
}
int main()
{
int v,t,p,d;
int x,y;
long long l,r;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&v);
a[i]=v;
aa[i]=v;
val[++cnt]=v;
}
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d",&t);
if(t==){
scanf("%d%d",&p,&d);
q[i].t=t;
q[i].p=p;
q[i].d=d;
aa[p]+=d; //是累加的
val[++cnt]=aa[p];
}
else{
scanf("%I64d%I64d",&l,&r);
q[i].t=t;
q[i].l=l; //也可以将查询的l和r加入到离散的数据中去，这样二分查找的时候就不用考虑l和r不存在的问题，
q[i].r=r; //查找时，当hashval[mid]==m时返回mid就行，当然这样数组相对就要开大了。
}
}
sort(val,val+cnt+);
//for(int i=0;i<=cnt;i++)
// printf("%I64d ",val[i]);
//printf("\n"); nn=;
hashval[++nn]=val[];
for(int i=;i<=cnt;i++){
if(val[i]!=val[i-]){
hashval[++nn]=val[i];
}
}
//for(int i=1;i<=nn;i++)
// printf("%I64d ",hashval[i]);
//printf("\n"); for(int i=;i<=n;i++)
aa[i]=a[i];
sort(aa+,aa+n+); //这里pos数组存储的是初始序列在离散后的数组hashval中的位置，用于建树的初始化
//也可以不采用该方法，在建树时都设为0，然后在对初始序列一个个update即可
for(int i=;i<=n;i++){
pos[i]=binarySearch(aa[i],,nn);
} build(,,nn);
for(int i=;i<=m;i++){
if(q[i].t==){
x=binarySearch(a[q[i].p],,nn);
update(,,nn,x,,);
a[q[i].p]+=q[i].d;
x=binarySearch(a[q[i].p],,nn);
update(,,nn,x,,a[q[i].p]);
}
else{
x=binarySearch(q[i].l,,nn);
y=binarySearch(q[i].r,,nn);
//printf("%I64d %I64d %d %d\n",q[i].l,q[i].r,x,y);
if(x>nn||y<||x>y)
printf("0\n"); //可能会遇到l>r的情况，参见代码后面的例子
else
printf("%I64d\n",query(,,nn,x,y).ans);
}
}
return ;
} /*
4
20 30 10 -20
5 x y
2 -25 -20 2 2
1 2 -40
2 21 25 6 5 （这里l>r，一开始忽略了这种情况，导致运行到第二个程序的时候，查询一直往下，无法停止，导致MLE）
1 4 -10
2 -35 -30 1 1 附：叶子节点对应的数据：
-30 -20 -10 10 20 30
*/