普通树状数组

树状数组

普通的树状数组维护的信息及运算要满足 结合律 且 可差分，如加法、乘法、异或等。

Q1：为什么要满足 结合律？

A1：说明要求的区间信息可能是由若干个已知区间信息拼凑起来的，故需要满足结合律。

Q2：为什么要满足 可差分？

A2：说明要求的区间信息可能通过两个区间作差得出。

一维树状数组

不妨假设 $a$ 是原始序列，以往我们要求 $a$ 的区间 $[l,r]$ 的信息，需要遍历区间。

树状数组的核心是维护 若干个块状 的信息，然后将这若干个块状信息 结合 为我们需要的区间信息。

也就是 一个位置表达更多的信息，这样才能达到减少时间复杂度的效果。

怎么选择块的大小呢？

已知任意一个正整数 $i$ 都能被写成 二进制 的形式。

不妨设 $i$ 的二进制可以写成 $2^{k_1}+2^{k_2}+\cdots +2^{k_m}$ （$k_1<k_2<\cdots <k_m$）。

这样可以看做一个长度为 $i$ 区间的信息 被分成了 $m$ 块 信息。

所以，如果要求 $1\sim i$ 的区间信息，只需要知道这 $m$ 个块的信息就可以。

怎么维护这 $m$ 块信息呢？

可以令 $tree[i]$ 维护一个以 $i$ 为 右端点，大小为 $2^{k_1}$ 的区间信息。

此时就剩下了 $m-1$ 块区间。

设 $j=i-2^{k_1}$，不难发现 $j$ 的二进制表示恰好为 $2^{k_2}+\cdots +2^{k_m}$。

继续令 $tree[j]$ 维护一个以 $j$ 为右端点，大小为 $2^{k_2}$ 的区间。

而对于一个位置，只令其维护其 二进制最小的 $1$ 所代表的长度 的区间信息，这个值被称为 $lowbit$。

不难看出，只需要遍历 $m$ 个 $tree$ 的位置就能拼凑出 $[1,i]$ 的区间信息。

而遍历的方向就是，不断地用 $i$ 减去其 $lowbit$。

又因为 $m\le log(i)$，所以求出 $[1,i]$ 的区间信息只需要 $O(logn)$ 的复杂度。

于是得到了树状数组最核心的 状态设计：

$tree[i]$ 维护的是以 $i$ 为右端点，大小为 $lowbit(i)$ 的区间信息。

区间查询

要求 $[l,r]$ 的区间信息，可以先求出 $[1,r],[1,l]$ 的区间信息，然后再作差。

而求出 $[1,i]$ 的区间信息，需要从 $i$ 开始往下跳 $log(i)$ 次，直到跳到 $0$。

T getsum(int x) {
     T ans = 0;
     while (x) {
          ans += tree[x];
          x = x - lowbit(x);
     }
     return ans;
}

单点修改

要修改 $a[x]$ 的值，就需要在树状数组中同步修改能管辖到 $x$ 的所有位置。

因为 $x$ 是最小的能管辖到 $x$ 的位置，所以从 $x$ 开始一直往上跳，直到跳出范围即可。

设 $n$ 表示 $a$ 数组的大小，不难写出单点修改 $a[x]$ 的过程：

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18

template<typename T>

// 单点修改和区间查询的树状数组
struct Fenwick {
     vector <T> tree;
     int n;

     Fenwick(int _n) : n(_n), tree(_n + 2){}

     // 求 1~x 的前缀和
     T getsum(int x) {
          T ans = 0;
          int L = x;
          while (x) {
               ans += tree[x];
               x = x - lowbit(x);
          }
          return ans;
     }

     // 区间查询
     T get_range_sum(int l, int r) {
          return getsum(r) - getsum(l - 1);
     }

     // 单点修改，是为了 range_add 服务
     void add(int x, T k) {
          while (x <= n) {
               tree[x] += k;
               x += lowbit(x);
          }
     }

     static inline int lowbit(int x) {
          return x & (-x);
     }
};
void slove () {
	Fenwick<int> tree(n);
}

signed main () {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    slove();
}

带区间加的区间和

如何给区间 $[l,r]$ 都加上一个常数 $k$？

显然不能使用 $r-l+1$ 次单点修改，这样时间复杂度比直接遍历还劣。

考虑到实现单点修改是 $O(logn)$，实现区间查询是 $O(logn)$。

不妨 用单点修改来代替区间加。

给区间加上一个常数可以用 差分 解决，即给 $l$ 处加 $k$，$r+1$ 处减 $k$。

如果此时再去求区间和，应该怎么办？

考虑查询 $[1,l]$ 的区间和，则有
$$\sum _{i=1}^l\sum _{j=1}^i{d}_j$$
等价于
$$\sum _{i=1}^l{d}_i\times (l-i+1)=(l+1)\sum _{i=1}^l\times d_i-\sum _{i=1}^{l}i\times d_i$$
能转换为 ${\sum }_{i=1}^l{d}_i\times (l-i+1)$ 是因为每个 $d_i$ 都被加了 $l-i+1$ 次。

然后拆开括号得到 $(l+1){\sum }_{i=1}^l\times d_i$ 和 ${\sum }_{i=1}^{l}i\times d_i$。

拆开是因为一个树状数组是 无法同时维护 包含 两个变量 $l,i$ 的表达式。

此时就只需要维护 $d_i$ 和 $c_i=i\times d_i$ 这两个数组。

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18

template<typename T>

// 区间修改 + 区间查询
struct Fenwick {
     vector <T> tree_d, tree_dx;
     int n;

     Fenwick(int _n) : n(_n), tree_d(_n + 2), tree_dx(_n + 2){}

     // 求 1~x 的前缀和
     T getsum(int x) {
          T ans1 = 0, ans2 = 0;
          int L = x;
          while (x) {
               ans1 += tree_d[x];
               ans2 += tree_dx[x];
               x = x - lowbit(x);
          }
          return (L + 1) * ans1 - ans2;
     }

     // 暴露在外的接口，求范围值
     T get_range_sum(int l, int r) {
          return getsum(r) - getsum(l - 1);
     }

     // 单点修改，是为了 range_add 服务
     void add(int x, T k) {
          while (x <= n) {
               tree_d[x] += k;
               tree_dx[x] += k * x;
               x += lowbit(x);
          }
     }

     // 暴露在外的接口，给区间 [l, r] 加上 x
     void range_add(int l, int r, T x) {
          add(l, x);
          add(r + 1, -x);
     }

     static inline int lowbit(int x) {
          return x & (-x);
     }
};
void slove () {
	Fenwick<int> tree(n);
}

signed main () {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    slove();
}