树状数组详解：原理、实现与代码示例

树状数组详解：原理、实现与代码示例

树状数组（Binary Indexed Tree，简称BIT）是一种用于高效处理数组区间查询和单点修改的数据结构。它在算法竞赛和实际开发中都有广泛应用，特别是在需要频繁进行前缀和计算的场景中。

树状数组的两个主要功能

1. 单点修改：对某个位置上的数加上一个数
2. 区间查询：动态地求某一个位置的前缀和

树状数组的时间复杂度为O(logn)，在只有查询操作的情况下，前缀和算法的时间复杂度为O(1)。因此，如果只有查询需求，优先使用前缀和算法。

原理

树状数组的空间复杂度和原数组一样，都是一个一维数组。其核心思想是通过二进制表示中的低位0的个数来组织数据。

层数的定义

观察一个数的二进制表示，末尾有几个连续的0，就有k个连续的0，那么这个数就在第k层。

例如：

• 1 (0001) 在第0层
• 2 (0010) 在第1层
• 4 (0100) 在第2层

树状数组中每个元素c[x]表示的范围如下图所示：

通过lowbit(x)函数可以返回最后一个1所代表的实际数值。如果这个数有k个0，那么就会返回2^k。

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

操作实现

求和操作

利用递归求和：假设我们要求x的前缀和

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

更新操作

对某一个数加上一个数，在树状数组上，只会对这个数和与这个数相距lowbit(x)的数造成影响

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

结点x的父节点是x + lowbit(x)。

时间复杂度分析

更新操作

相当于在数的二进制表示后面不断添加0，最多有logn位，所以时间复杂度为O(logn)。

求和操作

相当于不断往后添加1，与更新操作同理，时间复杂度为O(logn)。

例题

下面是一个完整的树状数组实现示例：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];   //原数组
int c[N];   //树状数组
int n,m,k,a,b;

int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}

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

void update(int a,int b)    //表示第a个数加b
{
    for(int i = a; i <= n; i += lowbit(i)) c[i] += b;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> q[i];
        //初始树状数组法一:
        //一开始q[i]都是0,接着往树状数组的的各个位置上插入q[i]
        update(i,q[i]);
    }
    //初始树状数组法二:
    //根据树状数组的定义进行初始化
    /*for (int i = 1; i <= n; i ++ )
    {
        for(int j = i; j > i - lowbit(i); j--)
        {
            c[i] += q[j];
        }
    }*/
    while(m--)
    {
        cin>>k>>a>>b;
        if(k == 0) cout << get_sum(b) - get_sum(a - 1) << endl;
        else update(a,b);
    }
    return 0;
}

这个示例展示了如何初始化树状数组、进行单点更新和区间查询。通过这个实现，可以高效地处理大规模数据的前缀和计算问题。