树状数组区间修改和区间求和
2020-12-13 03:18
标签：ons lib otto cpp 一个 sans 树状 microsoft style 最一般树状数组能做到的操作是单点修改，区间求和，都是log(n)级别的。原理就是用树状数组维护a[i]的部分和。 想要做到修改区间，求单点值也很简单，用树状数组维护a[i]的差分数组d[i]的部分和既可。 那么，如何同时做到区间求和，区间修改呢？ 有人可能会说了，如果是区间求和区间修改的话，直接写线段树不就好了吗？ 但是，从代码长度来看（dalao请无视），显然使用树状数组在考场上出错率会小一些, 回归正题。我们知道，想要达到log(n)级别的区间修改需要修改d[i]，那么在修改d[i]的情况下想要区间求和，我们就应该维护这个： 找出d[i]与a[i]的前缀和的关系，并用树状数组维护这个关系。 那么如何找关系呢？这里需要一点点数学证明： 我们设sum(i)=a[1]+a[2]+a[3]+······+a[i]， 则可知 sum(i)=(d[1])+(d[1]+d[2])+(d[1]+d[2]+d[3])+······+(d[1]+d[2]+d[3]+······+d[i])， 所以 sum(i)=i*d[1]+(i-1)*d[2]+(i-2)*d[3]+······+1*d[i]， 所以 sum(i)=∑(j从1到i)(i-j+1)d[j]， 最后一步化简后，我们得到这样一个式子： sum(i)=(i+1)∑(j从1到i)d[j]-∑(j从1到i)j*d[j] 即我们需要用树状数组分别维护d[i]的和和i*d[i]的和既可。 下面上代码： 树状数组区间修改和区间求和 标签：ons lib otto cpp 一个 sans 树状 microsoft style 原文地址：https://www.cnblogs.com/CYHeimu/p/11058205.html而且比较爽QWQ。 1#include
2#include
3#include
4#include
5using namespace std;
6
7long long n,m;
8long long c1[100010],c2[100010];
9
10void update(long long x,long long k)
11{
12 long long i=x;
13 while(x14 {
15 c1[x]+=k;
16 c2[x]+=i*k;
17 x+=x&-x;
18 }
19 return;
20}
21
22long long sum(long long x)
23{
24 long long ans=0;
25 long long i=x;
26
27 while(x>0)
28 {
29 ans+=c1[x]*(i+1);
30 ans-=c2[x];
31 x-=x&-x;
32 }
33 return ans;
34}
35
36int main()
37{
38 long long ord,x,y,k;
39 long long a,b=0;
40
41 scanf("%lld%lld",&n,&m);
42 for(long long i=1;i43 {
44 scanf("%lld",&a);
45 update(i,a-b);
46 b=a;
47 }
48 for(long long i=1;i49 {
50 scanf("%lld",&ord);
51 if(ord-1)
52 {
53 scanf("%lld%lld",&x,&y);
54 printf("%lld\n",sum(y)-sum(x-1));
55 }
56 else
57 {
58 scanf("%lld%lld%lld",&x,&y,&k);
59 update(x,k);
60 update(y+1,-k);
61 }
62 }
63 return 0;
64}