树状数组+差分

发表于 更新于 分类于 阅读次数： 本文字数： 6k
树状数组虽然简单好写，但是只能进行单点修改还是尽显劣势，然而，我们知道差分可以让区间修改简化为单点修改，这两者结合可以打出酷炫的组合技。

差分

差分就是数据之间的差，设原数组为\(a_i\)差分数组为\(b_i\),那么\(b_i=a_i-a_{i-1}\)，这是一个辅助数组，用来对数组进行区间修改的操作。

原理

首先，前缀和和差分互逆，前缀和数组通过差分可以得到原数组，而差分数组求前缀和也是原数组，即：\(\Sigma_{i=1}^nb_i = \Sigma_{i=1}^na_i-a_{i-1} = a_1-a_0+a_2-a_1+...+a_n-a_{n-1}=a_n-a_0=a_n\)

如果我们想要将区间\([a,b]\)都加上\(x\)，执行\(q\)次操作，那么为了不以\(O(nq)\)的时间复杂度进行，我们可以在差分数组上进行修改：让\(b_a\)加上\(x\)而\(b_{b+1}\)减去\(x\)，这样操作后通过前缀和求出\(a_i\)，对于\(1\le i<a\)的数没有影响，对于\(a\le i \le b\)，求和时多了\(x\)，因此每个数相当于都加上了\(x\)，而对于\(i>b\)，求和时加上了\(x\)又减去了\(x\)，实际上没有影响。因此，通过这样的方式，给定多次修改，我们只需要对差分数组进行操作，最后再求前缀和就能得到最终的数组了，时间复杂度为\(O(n+q)\)。

树状数组

树状数组是一种维护区间信息的数据结构，一般支持单点修改和区间查询。要求维护的信息及运算满足结合律和可差分（即可以通过\(a\circ b\)和\(a\)求出\(b\)），这是因为我们获得\([a,b]\)区间信息是通过\([1,b]\)的信息减去\([1,a-1]\)得到的。树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。

原理

以使用树状数组\(t_i\)维护数组\(a_i\)​维护区间和为例。（这里下标均从1开始）

首先我们定义lowbit(i)表示将\(i\)写为二进制后从右到左出现的第一个\(1\)的位置，除了这个位置为1以外，把其余位置都写成0的数字，例如：lowbit(1)=1，因为1的二进制就是1，从右到左出现的第一个\(1\)就是第一位，lowbit(2) = 2, lowbit(4) = 4,lowbit(14)=2，因为2，4，14分别写成二进制是10，100，1110，分别被看成了10，100，0010。

lowbit(i)的计算方法为：i & (-i)，这是因为补码表示中，真值为负数写成补码的一个技巧是把除符号位的所有位都取反，然后在末尾加一。假设原来的数为...100000，全部取反之后变成...011111，再加1变为...100000，此时省略号中所有数都是取反后的，因此与运算生效的只有一位，因此lowbit(x) = x & (-x)。

我们设\(t_i\)维护的是区间\([x,i]\)之和，长度一共是\(2^k\)，更形象地说，\(t_i\)维护的是右端点为\(i\)，区间长度为\(2^k\)的闭区间，其中\(2^k\)表示lowbit(i)的值。

举个例子：

$t_1 = a_1 $，lowbit(1) = 1，维护长度为1，末尾为\(1\)的区间和。

$t_2 = a_1+a_2 $，lowbit(2) = 2，维护长度为2，末尾为\(2\)的区间和。

$t_3 = a_3 $，lowbit(3) = 1，维护长度为1，末尾为\(3\)的区间和。

$t_4 = a_1+a_2+a_3+a_4 $，lowbit(4) = 4，维护长度为4，末尾为\(4\)的区间和。

这样操作之后，如果我们想要查询\([2,3]\)的区间和，需要使用\([1,3]\)的区间和减去\([1,1]\)的区间和，对于\([1,a]\)的区间和的求法是：将\(a\)写成二进制的形式，先加上\(t_a\)，然后\(t_a = t_a - lowbit(a)\)，这样一直循环直到\(a = 0\)。即：\(sum[1,3] = t_3 + t_{3-lowbit(3)}=t_3+t_{2} = a_1 + a_2 + a_3\)，这里3-lowbit(3)=2,2-lowbit(2)=0结束。为什么这么做呢？因为我们第一次操作后得到了\([i-lowbit(i)+1,i]\)的和，还需要得到\([1,i-lowbit(i)]\)的和，所以再按照相同规则继续下去。

对于单点修改，我们要修改\(a_x\)，所以\(t_x\)一定会被影响，继续考虑其他位置。当\(i<x\)时，由于我们\(t_i\)数组的定义，一定不会受到影响，所以不用修改。当\(i>x\)时，假设\(j\)位置受到影响，那么\(t_j\)的区间一定要包含\(i\)，即lowbit(j) > j - i，实际上，区间包含存在一个性质：对于\(t_x,t_y,x\le y\)，要么\(t_x\)和\(t_y\)不交，要么\(t_y\)包含\(t_x\)（证明略），实际上x<y<x+lowbit(x)时，有\(t_x,t_y\)不交，那么我们单点修改的过程实际上就是先修改t[x]，然后y = x + lowbit(x)，继续修改\(t_y\)，重复这个过程，直到超过范围。

模版

注意这里0-index和1-index的转换。单点修改要提前减去1，区间和不用减，\([l,r]\)的和要把\(l\)减去1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

时间复杂度：单次修改\(O(\log n)\)，区间查询\(O(\log n)\)

P3374 【模板】树状数组 1

操作：将一个位置的数加上\(x\)​，求出某一个区间的和。

考验模版的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    Fenwick bit(n);
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        bit.add(i, v);
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        x--;
        if (op == 1) {
            bit.add(x, y);
        } else {
            cout << bit.rangeSum(x, y) << endl;
        }
    }
}

P3368 【模板】树状数组 2

操作：将一个区间的数加上\(x\)，求出某一个位置的数。

为了给下一道题做铺垫，使用树状数组维护差分数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n, m;
    cin >> n >> m;
    int last = 0;
    Fenwick bit(n);
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        bit.add(i, v - last);
        last = v;
    }
    for (int i = 0; i < m; i++) {
        int op, x, y, k;
        cin >> op >> x;
        if (op == 1) {
            cin >> y >> k;
            x--;
            bit.add(x, k);
            bit.add(y, -k);
        } else {
            cout << bit.sum(x) << "\n";
        }
    }
}

树状数组+差分

区间修改

树状数组虽然简单好写，但是只能进行单点修改还是尽显劣势，然而，我们知道差分可以让区间修改简化为单点修改，这两者结合可以打出酷炫的组合技。

如果题目的操作是区间修改+区间查询，我们首先将数组差分，有\(b_i = a_i-a_{i-1}\)，我们知道差分之后有\(\Sigma_{j=1}^ib_j=a_i\)，那么如果要求区间和，就是\(\Sigma_{i=l}^r\Sigma_{j=1}^ib_i\)。我们不妨先考虑\(l=1\)的情况，因为区间和是可以差分的。所以进一步化简，有： \[ \sum_{i=1}^r\sum_{j=1}^ib_i\\=\sum_{i=1}^r(r-i+1)*b_i=\\(r+1)\sum_{i=1}^rb_i-\sum_{i=1}^r(i*b_i) \]

我们使用两个树状数组，分别维护\(b_i\)和\(ib_i\)，那么区间和的结果就是分别查询后相减。

LOJ 树状数组 3 ：区间修改，区间查询

操作：将一个区间的数加上\(x\)，给定一个区间，求出区间和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n, 0);
    }
    void add(int x, int v) {
        for (int i = x + 1; i <= n; i += i & (-i)) {
            a[i - 1] += v;
        }
    }
    int sum(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & (-i)) {
            res += a[i - 1];
        }
        return res;
    }
    int rangeSum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
    int n, q;
    cin >> n >> q;
    Fenwick bit1(n), bit2(n);
    int last = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        bit1.add(i, v - last);
        bit2.add(i, (i + 1) * (v - last));
        last = v;
    }
    for (int i = 0; i < q; i++) {
        int op, l, r, x;
        cin >> op >> l >> r;
        l--;
        if (op == 1) {
            cin >> x;
            bit1.add(l, x);
            bit1.add(r, -x);
            bit2.add(l, (l + 1) * x);
            bit2.add(r, (r + 1) * -x);
        } else {
            auto query = [&](int x) {
                return (x + 1) * bit1.sum(x) - bit2.sum(x);
            };
            cout << query(r) - query(l) << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

逆序对问题

在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个 逆序（inversion）或反序。这里的比较是在自然顺序下进行的。

在一个排列里出现的逆序的总个数，叫做这个置换的 逆序数。排列的逆序数是它恢复成正序序列所需要做相邻对换的最少次数。因而，排列的逆序数的奇偶性和相应的置换的奇偶性一致。这可以作为置换的奇偶性的等价定义。

我们可以利用树状数组求逆序对数，具体做法如下：

  1. 离散化：如果数组中元素的范围很大，需要对数组进行离散化处理，将每个元素映射到一个小范围内（比如 1 到 n），使得树状数组可以处理较小的索引范围。
  2. 我们新开一个数组用来记录下标，使用iota()函数。然后对该数组进行排序，排序的规则是：按照原数组从大到小排序，如果值相同的话下标大的在前。
  3. 遍历新数组\(A_i\)，在树状数组中查询\(A_i-1\)的前缀和，他表示在当前元素的右边有多少元素小于\(A_i\),这些就是满足逆序对的元素数量。计算完后，将当前元素加入到树状数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int>p(n+1);
Fenwick bit(n+1);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j){
  	if(pre[i] != pre[j]){
      	return pre[i] > pre[j];
    }
  	return i > j;
});
for(auto i : p){
    ans += bit.sum(i);
    bit.add(i, 1);
}