一、题目：

二、题解：

在单点修改中，我们用t[i]来维护原数组

2.1:在区间修改中，我们将维护原数组的差分数组

• 接下来，让我们来回顾一些差分的性质
  
• 此时，假设我们需要求$a1+a2+a3+a4$的和，并且是直接通过$d[i]$来求，我们可以发现：
  
• 推广到$n$可以得到
  

2.2：因此我们可以维护两个数组，一个为$td[i]$（PS：因为n+1是常量），一个为$i\ast td[i]$，这样就可以直接通过$d[i]$来进行区间查询

• $td[i]$表示的是：$d[i]$从$[i-lowbit(i)+1,i]$的值（PS:相当于差分时，对差分数组做前缀和映射到原数组)
  

2.3:相较于单点修改的差别

1、变量定义：

ll td[N];  //维护树状数组的差分
ll tdi[N]; //维护td[i]*i

2、更新树状数组–>更新树状差分数组的单点修改(相当于在 $i$ 处$+a[i]$)

	//初始化树状差分数组for (int i = 1; i <= n; i++) {update(i, a[i]);update(i+1,-a[i]);}

3、对于操作1（区间修改）变化：运用差分性质($(a[l]->a[r])+v==(d[l]+v),d[r+1]-v$)

		int op; cin >> op;if (op == 1){ll l, r , v; cin >> l >> r >> v;update(l, v);   //维护差分数组update(r+1,-v);}

4、$update()$更新函数的变化：

• 1）：与单点修改思路一致，差分数组（$td[i]$）对于其每一个数字的管辖区间都$+v$
• 2）：对于$tdi[i]$，也就是$i\ast td[i]$，每一个元素都应该$+$传入函数的原始值$（x\ast v）$如图：而不应该是$(i\ast v)$因为此时是$tdi[x]$的增加影响了$tdi[i]$的值，如果写成了$(i\ast v)$就变成了$（4\ast 2）$，但是实际应该为$(3\ast 2)$
  

void update(ll x, ll v)   //第 x 个值变化了 v
{for (int i = x; i <= n; i += lowbit(i)){td[i] += v; //维护tdtdi[i]+=x*v; //维护td*i}
}

5、$getsum()$求和函数的变化

• 1、由推广公式可以得到求和函数
• 2、类比前缀和的性质，求解$getsum(r)-getsum(l-1)$即可得出$[l,r]$的和
  

ll getsum(ll x)   //区间查询
{ll sum = 0;for (int i = x; i >= 1; i-=lowbit(i)){sum += (x+1)*td[i]-tdi[i];}return sum;
}
ll l, r; cin >> l >> r;
cout << getsum(r) - getsum(l - 1) << '\n';

三、完整代码如下：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 3e5 + 7;
ll a[N];
ll td[N];  //维护树状数组的差分
ll tdi[N]; //维护td[i]*i
ll n, q;ll lowbit(ll x)   //树状数组底层函数
{return x & -x;
}void update(ll x, ll v)   //第 x 个值变化了 v
{for (int i = x; i <= n; i += lowbit(i)){td[i] += v; //维护tdtdi[i]+=x*v; //维护td*i}
}ll getsum(ll x)   //区间查询
{ll sum = 0;for (int i = x; i >= 1; i-=lowbit(i)){sum += (x+1)*td[i]-tdi[i];	//求和公式}return sum;
}void solve()
{cin >> n >> q ;for (int i = 1; i <= n; i++) cin >> a[i];//初始化树状数组for (int i = 1; i <= n; i++) {update(i, a[i]);update(i+1,-a[i]);}while (q--) //q次询问{int op; cin >> op;if (op == 1){ll l, r , v; cin >> l >> r >> v;update(l, v);   //维护差分数组update(r+1,-v);}else{ll l, r; cin >> l >> r;cout << getsum(r) - getsum(l - 1) << '\n';}}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1; //cin >> _;while (_--) solve();system("pause");return 0;
}