树状数组的区间修改查询

树状数组,是一种常数很低的$O(n\dot~log_2n)$的数据结构

不过作用范围不大。

我们设原数组为$A$

和它的差分数组$C,C_i=a_i-a_{i-1}$

我们发现$A_i=\sum_{i=1}^iC_i$

所以求前缀和$A_{1\dots n}$可以转换成

$S=\sum_{i=1}^nA_i=\sum_{i=1}^n\sum_{j=1}^iC_j=\sum_{j=1}^nC_{j}\sum_{i=1}^n[j\le i]=\sum_{j=1}^n((n-j+1)\dot~C_j)$

我们发现这字母太丑了,换一个:$S=\sum_{i=1}^n((n-i+1)\dot~C_i)$

然后我们维护$(n-i+1)C_i$

可是询问总是会变的,假如询问变成$n’$

$S’=\sum_{i=1}^{n’}A_i=\dots=\sum_{i=1}^{n’}((n’-i+1)\dot~C_i)\not=\sum_{i=1}^{n’}((n-i+1)\dot~C_i)$

我们于是考虑将$S$与$i$联系起来

我们可以维护$D_i=\sum_{j=1}^i(j-1)\dot~C_j$,还有$E_i=\sum_{j=1}^iC_j$

因为这样就与$n$没关系了

维护也很好维护的

然后我们可以得到$S=\sum_{i=1}^nA_i=\dots=\sum_{i=1}^n(n\dot~C_j-(i-1)\dot~C_j)=nD_i-E_i$

然后给个模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define N 100010
long long n,q,bit1[N],bit2[N];
void add(long long *b,long long x,long long w)
{
while(x<=n)
{
b[x]+=w;
x+=x&(-x);
}
}
long long query(long long *b,long long x)
{
long long r=0;
while(x)
{
r+=b[x];
x-=x&(-x);
}
return r;
}
int main()
{
n=read();
q=read();
fr(i,1,n)
{
long long a=read();
add(bit1,i,a);
add(bit2,i,a*(i-1));
add(bit1,i+1,-a);
add(bit2,i+1,-a*i);
}
while(q--)
if(read()&1)
{
long long x=read(),y=read(),k=read();
add(bit1,x,k);
add(bit2,x,(x-1)*k);
add(bit1,y+1,-k);
add(bit2,y+1,-k*y);
}
else
{
long long x=read(),y=read();
long long ans=(y*query(bit1,y)-(x-1)*query(bit1,x-1));
ans-=query(bit2,y)-query(bit2,x-1);
printf("%lld\n",ans);
}
return 0;
}