Jiez19971225‘s Blog

做自己爱做的事

0%

树状数组

发表于 更新于 分类于   |   字数统计: 800(字)   |   阅读时长: 3(分)

核心

树状数组是一种用来解决区间单点更新，区间求和问题的简单数据结构。其核心思想在于二进制特殊性质。

1
2
3
4
int lowbit(int x)
{
    return x & (-x);
}

lowbit

lowbit 函数的作用是取得 x 最右边一个 1 对应的数值。 如果 x 的二进制可以表示为 00010010，那么 lowbit 的结果为 2。怎么做到的呢？-x 的补码是 x 按位取反加 1，0010 变成 1101 +1 = 1110 ，-x 从右数第一个 1 的位置对应 x 从右数第一个 x 的位置，其他均取反。
如此便可以取得所要得到的数。
得到了这个数又有什么用呢。可以看下表

普通数组 a 树状数组 c 解释 二进制
1 1 a[1] 0001
2 3 a[1]+a[2] 0010
3 3 a[3] 0011
4 10 a[1]+a[2]+a[3]+a[4] 0100
5 5 a[5] 0101
6 11 a[5]+a[6] 0110
7 7 a[7] 0111
8 36 a[1]+…+a[8] 1000
9 9 a[9] 1001

对于一个位置，看它的二进制，这个位置保存的元素个数就是其二进制最右边 1 代表的大小，保存从去掉最右边 1 到加上最右边 1 的位置之间的数据（左开右闭）。
这样表述很不清楚，直接距离，看 c[6]位置，6 的二进制是 0110，去掉最右边 1 是 0100，即十进制的 4，它保存的是(4,6]之间的数据。

那么对于求和操作，就变成了不断找右边的 1 的过程。

对于更新操作，我们要同时更新其之后的父节点。
当我们修改 a[i]的值时，可以从 c[i]往根节点一路上溯，调整这条路上的所有 C[]即可，对于节点 i，父节点下标 p=i+lowbit(i)

树状数组多用于求逆序对，原理是将序列按顺序插入树状数组时，每次统计比当前数小的元素数量 sum，则与当前数构成逆序的对数有 i-sum
可以离散化数据，我们不关心具体元素的数值，只关心其对应关系。

代码实现

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
int n;
int c[maxn];
int lowbit(int x)
{
    return x & (-x);
}
void update(int i, int v)
{
    while (i < n)
    {
        c[i] += v;
        i += lowbit(i);
    }
}
int getsum(int i)
{
    int sum = 0;
    while (i > 0)
    {
        sum += c[i];
        i -= lowbit(i);
    }
}

int main()
{
    freopen("data.in", "r", stdin);
    n = 10;
    for (int i = 1; i <= n; i++)
    {
        int tmp;
        cin >> tmp;
        update(i, tmp);
    }
    for (int i = 1; i <= 10; i++)
    {
        cout << c[i] << endl;

    }
}

扩展到二维

问题：一个由数字构成的大矩阵，能进行两种操作

  • 对矩阵里的某个数加上一个整数（可正可负）
  • 查询某个子矩阵里所有数字的和,要求对每次查询，输出结果。

一维树状数组很容易扩展到二维，在二维情况下:数组 A[][]的树状数组定义为：

其相应的更新与求和操作也很容易类比出来，这里就不做说明了。