支持区间修改的树状数组

原理

对于一个数组(a)，以及(a)的差分(c)，显然有(c[i]=a[i]-a[i-1])
那么对于数组a的前缀和有
(sum_{i=1}^n{a_i}=c[1]+(c[1]+c[2])+...(c[1]+c[2]+...+c[n]))
进一步的：
(sum_{i=1}^n{a_i}=c[1]*n+c[2]*(n-1)+...+c[n]*(n-n+1))
展开括号内
(sum_{i=1}^n{a_i}=c[1]*n+c[2]*n+...+c[n]*n-(c[1]*(1-1)+c[2]*(2-1)+...+c[n]*(n-1)))
即为
(sum_{i=1}^n{a_i}=n*sum_{i=1}^n{c[i]}-sum_{i=1}^n{c[i]*(i-1)})
因此维护一个前缀和数组需要维护两个差分前缀和(c[i])和((i-1)*c[i])，对应为维护(sum_{i=1}^n{c[i]})，(sum_{i=1}^n{(i-1)*c[i]})
这里使用两个树状数组对上述差分数组前缀和维护，分别命名为(tr)和(tr1)。

实现

首先明确基本树状数组的两个基本操作：区间查询和单调查询。使用树状数组维护前缀和：

区间查询 ( ext{query}(k))，1到k之间的前缀和(sum_{i=1}^k{a[i]})
单点修改 ( ext{add}(k,x)), (a[k]+=x)

那么对于本文中的支持区间修改的树状数组有以下操作：
1.区间修改 ( ext{add}(l,r,k))(l和r包含),等效于操作( ext{add1(l,x)}),( ext{add1}(r+1,-x))和( ext{add2}(l,(l-1)*x)),( ext{add2}(r+1,r*(-x)))(差分性质定义)
2.区间查询 ,(querysum(k)),等效于操作(k* ext{query1}(k)*k- ext{query2}(k))

操作

基本树状数组

实现了(O(log(n)))单点修改和区间查询。
支持单点修改，区间查询，单点查询。

int n, m;
ll a[maxn];
ll tr[maxn];  //树状数组1用于维护差分前缀和$sum_{i=1}^n{c[i]}$
ll tr1[maxn]; //树状数组2用于维护差分前缀和$sum_{i=1}^n{(i-1)*c[i]}$
int lowbit(int x) { return x & -x; }
void add(ll tr[], int l, ll k) {
  for (int i = l; i <= n; i += lowbit(i)) tr[i] = (tr[i] + k) % mod;
}
ll query(ll tr[], int r) {
  ll res = 0;
  for (int i = r; i; i -= lowbit(i)) res = (res + tr[i]) % mod;
  return res;
}

初始化

void init(int nn) {
  n = nn + 2;//防止空间越界
  for (int i = 0; i <= n; i++) tr[i] = tr1[i] = 0;
}

区间修改

//[l,r]区间修改+x
void add(int l, int r, int x) {
  add(tr, l, x);
  add(tr, r + 1, -x);
  add(tr1, l, 1ll * (l - 1) * x);
  add(tr1, r + 1, 1ll * r * (-x));
}

区间查询

查询(sum_{i=1}^ka[i])，即查询([1,k])内的前缀和

//区间查询原数组sum(a[1,k])
ll querysum(int k) {
  return (1ll * query(tr, k) * k)  - query(tr1, k);
}

区间修改

在(a[l]...a[r])区间加上(x).

//[l,r]区间修改+x
void add(int l, int r, int x) {
  add(tr, l, x);
  add(tr, r + 1, -x);
  add(tr1, l, 1ll * (l - 1) * x);//防止暴int
  add(tr1, r + 1, 1ll * r * (-x));
}

复杂度分析

实质是两个树状数组来维护着差分前缀和，其中空间是3倍的区间长度,(O(3*n))
时间复杂度：
在以下操作均为(O(log(n)))：

区间同加x
区间查询
单点查询
单调同加x

相比线段树空间复杂度(O(4*n))要小
时间复杂度相同。

编程复杂度差不多（~~都好难orz~~）

整合模板

题目传送门

#define judge
// Author: oceanlvr
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static int faster_iostream = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  return 0;
}();
const int maxn = 1e6 + 10;
const int mod = 772002 + 233;
int n, m;
ll a[maxn];
ll tr[maxn];  //树状数组1
ll tr1[maxn]; //树状数组2
int lowbit(int x) { return x & -x; }
void add(ll tr[], int l, ll k) {
  for (int i = l; i <= n; i += lowbit(i)) tr[i] = (tr[i] + k) % mod;
}
ll query(ll tr[], int r) {
  ll res = 0;
  for (int i = r; i; i -= lowbit(i)) res = (res + tr[i]) % mod;
  return res;
}
//[l,r]区间修改+x
void add(int l, int r, int x) {
  add(tr, l, x);
  add(tr, r + 1, -x);
  add(tr1, l, 1ll * (l - 1) * x);
  add(tr1, r + 1, (1ll * r * (-x)%mod+mod)%mod);
}
//区间查询原数组sum(a[1,k])
ll querysum(int k) {
  return (((1ll * query(tr, k) * k) % mod - query(tr1, k) % mod) % mod + mod) %
         mod;
}
void init(int nn) {
  n = nn + 2;
  for (int i = 0; i <= n; i++) tr[i] = tr1[i] = 0;
}
/*------------------------------------------------------------------------------*/
//按题目要求区间[l,r]修改 [l+1,r]+d,[l,l]+a0,[r+1,r+1]-前面两个的和
void addad(int l, int r, int a0, int d) {
  add(l, l, a0);                     //单点l上+a0
  if (l + 1 <= r) add(l + 1, r, d);  //区间[l+1,r] +d
  add(r + 1, r + 1,
      (-(a0 + (1ll * (r - l) * d)) % mod + mod) % mod);  //单点r+1 -前面两个的和
}
//区间查询原数组sum(a[1,k])
int queryad(int k) { return querysum(k); }

int op;
int main() {
#ifndef judge
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i],a[i]%=mod;
  init(n);
  for (int i = 0; i < m; i++) {
    cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      //(y+1)y/2
      //对[x,x+y-1]加上一个-1
      int l = x, r = min(x + y - 1, n);
      addad(l, r, y, -1);
    } else if (op == 2) {
      int x;
      cin >> x;
      cout << (a[x] + queryad(x)) % mod << endl;
    }
  }

  return 0;
}

参考链接：树状数组区间加等差数列