如何将树状数组应用于长尾词的区间修改与区间查询问题？

本文共计765个文字，预计阅读时间需要4分钟。

树状数组的操作包括——区间修改 + 区间查询 + 树状数组的操作是对一组数据进行快速修改查询操作，最基本的功能是单点修改 + 区间查询。其中，威胁较大的是区间修改 + 单点查询（使用数组del[i]表示）。

树状数组之————区间修改+区间查询

树状数组的工作是 对一组数据进行快速修改查询操作

最基本的功能是 单点修改+区间查询。

然后厉害的是 区间修改+单点查询（用数组del[i]表示原数组a[i]-a[i-1]的值）

更厉害的来了。。。

区间修改+区间查询

用数组del[i]记录原数组a[i]与前一项和，即del[i]=a[i]-a[i-1]

求数组a的前n项和就是：

S(n) = a[1]+a[2]+...a[n]

= del[1] + (del[1]+del[2]) + .... + (del[1]+del[2]+....del[n])

= n*del[1] + (n-1)*del[2] + .... + 1*del[n]

= (n+1 -1)*del[1] + (n+1 -2)*del[2] + .... + (n+1 -n)*del[n]

= (n+1)*(del[1]+del[2]+ ... +del[n]) - (1*del[1] + 2*del[2] + ... + n*del[n])

= (n+1)*sum(del[i], 1<=i<=n) - sum(i*del[i], 1<=i<=n)

其实只需要求出(n+1)*sum(del[i]) ,和sum(i*del[i], 1<=i<=n)，相减即可

所以就用两个树状数组共同维护

用数组c1[i]维护del[i]

用数组c2[i]维护i*del[i]

对数组进行操作时，用时更新这两个数组即可。查询时，用上面推导的公式

对于那两个查询和修改函数不变，依然沿用最老套的模板

：

#include<stdio.h> #include<iostream> using namespace std; typedef long long ll; ll a[202020]; ll del[202020]; ll c1[202020];//维护del ll c2[202020];//维护x*del[x] ll n; void add(ll *c,ll k,ll num) { for(;k<=n;k+=k&-k) c[k]+=num; } ll read(ll *c,ll k)//查询区间1~k { ll sum=0; for(;k;k-=k&-k) sum+=c[k]; return sum; } ll sum(ll k) { return (k+1)*read(c1,k)-read(c2,k); } int main() { cin>>n; for(ll i=1;i<=n;i++){ cin>>a[i]; del[i]=a[i]-a[i-1]; add(c1,i,del[i]); add(c2,i,del[i]*i); } ll Q;cin>>Q; while(Q--) { ll oper;cin>>oper; if(oper==1) { ll a,b,num; cin>>a>>b>>num; add(c1,a,num); add(c1,b+1,-num); add(c2,a,num*a); add(c2,b+1,-num*(b+1)); } else { ll a,b;cin>>a>>b; ll sumr=sum(b); ll suml=sum(a-1); cout<<sumr-suml<<endl; } } }