树状数组进阶

一.区间修改,单点查询

原数组(A),有元素(a_1,a_2,a_3...a_n)

考虑差分数组(C),(c_1,c_2,c_3...c_n)

其中(c_i=a_i-a_{i-1})

这样,$a_i=sum_{j=1}^{i} c_j $

用树状数组维护前缀和

区间修改 (l,r,v)

   c[l]+=v;
   c[r+1]-=v;

单点查询 (p)

   cout<<query(p);

二.区间修改,区间查询

原数组(A),有元素(a_1,a_2,a_3...a_n)

考虑差分数组(C),(c_1,c_2,c_3...c_n)

其中(c_i=a_i-a_{i-1})

这样,$a_i=sum_{j=1}^{i} c_j $

通过这样,我们查询(A)数组的前缀和 (a_1...a_p)

得到 $ sum_{i=1}^{p} a_i = sum_{i=1}^{p} sum_{j=1}^{i} c_j$

进一步得到

$ sum_{i=1}^{p} a_i = sum_{i=1}^{p} (p+1-i) * c_i$

转换得到

$ sum_{i=1}^{p} a_i = (p+1) * sum_{i=1}^{p} c_i - sum_{i=1}^{p} i * c_i$

考虑差分数组(D),(d_1,d_2,d_3...d_n)
和(E),(e_1,e_2,e_3...e_n)

(d_i= c_i)

(e_i= i * c_i)

树状数组维护(D,E)数组的前缀和

模板题

[code]

#include <bits/stdc++.h>
using namespace std;
#define int long long

int read(){
	int x=0; char c; int flag=1;
	for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
	for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
	return x*flag;
}
const int N=1e5+10;

int a[N+10],c[N+10];
int d[N+10],e[N+10];
int lowbit(int x) { return x&(-x); }
void update(int x,int y){
    for(int i=x;i<=N;i+=lowbit(i))
    d[i]+=y;
    for(int i=x;i<=N;i+=lowbit(i))
	e[i]+=x*y;
}
int query(int x){
    int ret=0;
    for(int i=x;i>0;i-=lowbit(i))
    ret+=(x+1)*d[i];
    for(int i=x;i>0;i-=lowbit(i))
    ret-=e[i];
    return ret;
}
int n,m;

signed main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1];
	for(int i=1;i<=n;i++) update(i,c[i]);
	
	while(m--){
	    int opt=read();
	    if(opt==1){
		    int l=read(),r=read(),v=read();
		    update(l,v); update(r+1,-v);
		}else{
		    int l=read(),r=read();
		    printf("%lld
",query(r)-query(l-1));
		}
	}
	
	return 0;
}