树状数组
树状数组的区间修改区间查询
设差分数组\(c_i=a_i-a_{i-1}\)，
\[\because a_i= \sum_{1}^{i}c_i\]
\[\therefore\sum_{i=1}^x a_i=\sum_{i=1}^x\sum_{j=1}^ic_j =\sum_{i=1}^x (x-i+1)*c_i\]
\[\sum_{i=1}^x a_i=(x+1)\sum_{i=1}^x c_i-\sum_{i=1}^x c_i \times i\]
修改
void add(long long k,long long z)
{
for(long long i=k;i<=n;i+=(i& -i)) c[i]+=z,c1[i]+=(k-1)*z;
}前缀和查询
long long qsum(long long k)
{
long long ans=0;
for(long long i=k;i>0;i-=(i & -i)) ans+=(long long)c[i]*k-c1[i];
return ans;
}调用
add(x,y); add(x+1,-y);
版权声明：本文为ZUTTER原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。