OI-Knowledge：树状数组

在计算机科学中，树状数组（Binary Indexed Tree，BIT），也称为Fenwick Tree，是一种用于高效处理前缀和查询和更新操作的数据结构。树状数组非常适合解决动态数组的前缀和问题，可以在O(log n)时间内完成更新和查询操作。

基本概念

树状数组的核心思想是通过维护一组累加和来实现快速的前缀和查询和更新。其主要功能包括：

前缀和查询（区间查询）：在给定数组中快速求出前缀和。
单点更新：在给定数组中快速更新某个位置的值。

树状数组的结构

树状数组使用一个辅助数组 BIT 来维护信息。对于一个长度为 n 的数组，我们构建一个长度为 n+1 的 BIT 数组，其中 BIT[i] 表示从某个起始点到位置 i 的部分和。具体来说，BIT 的索引和原数组的索引之间有一定的映射关系，这种关系通过位运算来确定。

注意

树状数组的下标从1开始(同线段树root=1)

树状数组的操作

构建树状数组

初始化树状数组需要遍历原数组，并调用更新操作来填充 BIT 数组：

void buildBIT(vector<int>& arr, vector<int>& BIT) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        updateBIT(BIT, n, i, arr[i]);
    }
}

更新操作

更新操作用于在数组的某个位置添加一个值，并相应地更新 BIT 数组：

void updateBIT(vector<int>& BIT, int n, int index, int val) {
    index += 1; // BIT array is 1-indexed
    while (index <= n) {
        BIT[index] += val;
        index += index & (-index);
    }
}

查询操作

查询操作用于计算数组中从起始位置到某个位置的前缀和：

int queryBIT(vector<int>& BIT, int index) {
    int sum = 0;
    index += 1; // BIT array is 1-indexed
    while (index > 0) {
        sum += BIT[index];
        index -= index & (-index);
    }
    return sum;
}

示例

假设我们有一个数组 arr 为 [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3]，我们可以使用树状数组来进行快速的前缀和查询和单点更新。

正如之前所说，树状数组广泛应用于单点修改，区间查询的题目中

例题1：【模板】树状数组1

题目传送门：P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态(luogu.com.cn)

树状数组单点修改+区间查询模板题，实现代码如下：

%% 不同于一般使用树状数组所解决的单点修改+区间查询问题，此题需要我们解决的是区间修改+单点查询问题。简单分析不难发现通过把原来的队列转化为一个差分序列，就可以将区间修改变为单点修改，单点查询变为区间查询。 %%

实现代码如下：

/**********************************************************************************************************************
 * Problem: P3374 【模板】树状数组 1
 * URL: https://www.luogu.com.cn/problem/P3374
 * Description: Binary Indexed Tree
 * Created by Vegetabot on 6/8/2024.
**********************************************************************************************************************/
#include<bits/stdc++.h>
#define N 500003
using namespace std;
int lowbit(int x) {return x & (-x);}

int n, m;
vector<int> arr(N), bit(N);

void updateBIT(int index, int val) {
//    index += 1; // BIT array is 1-indexed
    while (index <= n) {
        bit[index] += val;
        index += lowbit(index);
    }
}
int queryBIT(int index) {
    int sum = 0;
//    index += 1; // BIT array is 1-indexed
    while (index > 0) {
        sum += bit[index];
        index -= lowbit(index);
    }
    return sum;
}

void buildBIT() {
    for (int i = 1; i <= n; i++) {
        updateBIT(i, arr[i]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;++i){
        scanf("%d", &arr[i]);
    }
    buildBIT();
    for(int i=1; i<=m; ++i) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            updateBIT(a, b);
        } else {
            cout << queryBIT(b) - queryBIT(a-1) << endl;
        }
    }
    return 0;
}

总结

树状数组是一种高效且易于实现的数据结构，特别适用于动态数组的前缀和问题。通过巧妙的位运算，树状数组能够在 O(log n) 的时间复杂度内完成更新和查询操作，极大地提高了性能。