C语言树状数组的实例详解

首先需要了解什么是树状数组。树状数组（Binary Indexed Tree，BIT），也叫做 Fenwick 树（树状数组的发明者是Peter M. Fenwick），是一个查询和修改复杂度都为 log(n) 的数据结构，与线段树类似，但使用起来比线段树更加方便以及简洁。

在该攻略中，我们将通过两条树状数组的实例，详细讲解树状数组，让读者更好地理解树状数组的基本原理和应用。

示例一：树状数组求和

首先我们介绍一下树状数组的基本结构：

int lowbit(int x) {
    return x & -x;
}

int c[maxn]; // 树状数组

其中lowbit是一个辅助函数，用来计算一个数的二进制表示下最低位的1所对应的数。即lowbit(x) = x & -x。

c数组用于存储树状数组。

接下来，我们来看一个求和的例子。假设我们有一个长度为n的数组a：

int a[maxn], c[maxn];
int n;

我们希望支持对a数组的区间求和，增加单个元素，查询单个元素等操作。我们可以使用树状数组来实现这些操作。具体的实现如下：

int lowbit(int x) {
    return x & -x;
}

int c[maxn]; // 树状数组

void update(int x, int v) {
    while(x <= n){
        c[x] += v;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0;
    while(x){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

其中，update函数用来增加某个位置上的值，query函数用来查询一个区间的和。例如，要修改第i个位置上的元素，需要调用update(i, v)方法。而要求1~j的区间和，则需要调用query(j) - query(i - 1)方法。

例如，对于一个数组a = {1,2,3,4,5}，我们可以先初始化树状数组：

for(int i = 1; i <= n; i++){
    update(i, a[i]);
}

接下来，我们可以调用query函数得到区间和：

int sum = query(j) - query(i - 1)

示例二：树状数组求逆序对

接下来，我们给出第二个例子：树状数组求逆序对。

逆序对的定义是，对于一个序列，如果 a[i] > a[j]，且 i < j，则称 (i, j) 为一个逆序对。求解逆序对的个数是一个常见的问题。

我们可以使用树状数组来实现求逆序对的过程。具体实现如下：

const int maxn = 500010;
int a[maxn], c[maxn], n;

inline int lowbit(int x){
    return x & (-x);
}

void add (int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)){
        c[i] += v;
    }
}

int sum (int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)){
        ans += c[i];
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    int ans = 0;
    for (int i = n; i > 0; i--){
        ans += sum(a[i] - 1);
        add(a[i], 1);
    }
    printf("%d\n", ans);
    return 0;
}

具体的实现如下：

• 先从后往前遍历序列，每遍历到一个数，就把它放到树状数组中，并且统计一下在它之前小于它的数的个数，即sum(a[i] - 1)。
• 最终的答案即为累加得到的逆序对数。

例如，对于一个序列a = {3, 1, 2}，我们可以先初始化树状数组：

for(int i = n; i > 0; i--){
    add(a[i], 1);
}

然后就可以累加逆序对数：

int ans = 0;
for (int i = n; i > 0; i--){
    ans += sum(a[i] - 1);
}
printf("%d\n", ans);

通过以上两个例子，我们可以看到树状数组在数据结构和算法中的广泛应用。