模板 树状数组

1.单点修改 区间查询

const int MAXN=1e5+8;
typedef long long ll;
int n;
ll a[MAXN];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,ll val){//单点修改
   while(x){
  	 	a[x]+=val;
	   	x+=lowbit(x);
   	}
}
inline ll sum(int x){//返回a[x]前缀和
    ll res=0;
    while(x){
    	res+=d[x];
    	x-=lowbit(x);
    }
    return res;
}
inline ll range_sum(int x,int y){//返回区间和
	return sum[y]-sum[x-1];
}

2.区间修改 单点查询

差分数组 $d\left[i\right]=a\left[i\right]-a[i-1]$d[i]=a[i]−a[i−1]，故 $a\left[i\right]=d\left[1\right]+d\left[2\right]+...+d\left[i\right]$a[i]=d[1]+d[2]+...+d[i]
维护 $d\left[i\right]$d[i] 前缀和即可维护 $a\left[i\right]$a[i]
若 $d\left[i\right]+=k$d[i]+=k 则： $a[j{]}^{\prime }=d[1]+d[2]+...+d[j]=a[j]+k$a[j]′=d[1]+d[2]+...+d[j]=a[j]+k 其中 $(i\le j)$(i≤j)
故区间 $[l,r]$[l,r]上加上k 等价于 $d\left[l\right]+k，d[r+1]-k$d[l]+k，d[r+1]−k

const int MAXN=1e5+8;
typedef long long ll;
int n;
ll d[MAXN];//差分数组
inline int lowbit(int x){return x&(-x);}
inline void add(int x,ll val){
   while(x){
  	 	d[x]+=val;
	   	x+=lowbit(x);
   	}
}
inline void range_add(int x,int y,ll val){//区间修改
    add(x,val);
    add(y+1,-val);
}
inline ll ask(int x){//返回a[x]
    ll res=0;
    while(x){
    	res+=d[x];
    	x-=lowbit(x);
    }
    return res;
}

3.区间修改 区间查询

$d\left[i\right]=a\left[i\right]-a[i-1]$d[i]=a[i]−a[i−1]
$dd\left[i\right]=i\ast d\left[i\right]$dd[i]=i∗d[i]
数组a前缀和 ${\sum }_{i=0}^{k}a\left[i\right]=a\left[1\right]+a\left[2\right]+...+a\left[k\right]=id\left[1\right]+(i-1)d\left[2\right]+...+d\left[k\right]$∑i=0k​a[i]=a[1]+a[2]+...+a[k]=id[1]+(i−1)d[2]+...+d[k]
$=(k+1)\ast \left(d\right[1]+d[2]+...+d[k\left]\right)-\left(d\right[1]+2d[2]+...+kd[k\left]\right)$=(k+1)∗(d[1]+d[2]+...+d[k])−(d[1]+2d[2]+...+kd[k])
所以，维护 $d\left[i\right]$d[i] 和 $dd\left[i\right]$dd[i] 即可。

const int MAXN=1e5+8;
typedef long long ll;
int n;
ll d[MAXN],dd[MAXN];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,ll val){//d和dd单点修改
    for(int i=x;i<=n;i+=lowbit(i)){
        d[i]+=val,dd[i]+=val*x;
    }
}
inline void range_add(int x,int y,ll val){
	add(x,val);
	add(y+1.-val);
}
inline ll sum(int x){//前缀和
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=(x+1)*d[i]-dd[i];
    return res;
}
inline ll range_sum(int x,int y){
	return sum(y)-sum(x-1);
}