树状数组笔记

警告

注：本文部分使用CSDN某文章，做了一些更改，并附上其他资料。

1.树状数组是什么？

树状数组是一个树形结构的数组，与二叉树的结构类似但又不同，在二叉树的结构上删除了一些节点。

二叉树结构：

树状数组结构：

树状数组可以解决什么问题呢？

可以解决大部分区间上面的修改以及查询的问题:

单点修改，单点查询
区间修改，单点查询
区间查询，区间修改

换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强。

树状数组和线段树的区别在哪？

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强但实现复杂的线段树(杀鸡焉用宰牛刀)。

树状数组的优点

优点：修改和查询操作复杂度于线段树一样都是 $O(log N)$ ,但是常数比线段树小，并且实现比线段树简单。
缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决。

树状数组和普通数组更新与查询的时间复杂度的对比

普通数组：

更新： $O(1)$
查询： $O(N)$

树状数组：

更新： $O(log N)$
查询： $O(log N)$

前置知识—lowbit(x)运算

如何计算一个非负整数n在二进制下的最低为1及其后面的0构成的数？

例如：

44 = ( 101100 )_2

最低为

1

和后面的

0

构成的数是

( 100 )_2 = 4

所以

l o w b i t ( 44 ) = l o w b i t ( ( 101100 )_ 2 ) = ( 100 ) 2 = 4

那么

lowbit

运算时怎么实现的呢？

44

的二进制

=(101100)_2

，我们对

44

的二进制数取反

+1

，也即

~44+1

,得到

-44

。

-44

的二进制

=(010100)_2

，然后我们把

44

和

-44

的二进制进行按位与运算，也即按位与得到,二进制

(000100)_2

，也就是十进制的

4

。

所以lowbit(x) = x&(-x)。

lowbit代码函数

CPP

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

单点修改，区间查询

所以我们在单点修改的同时，更新父节点就变得尤为简单，，例如我们对

a_i+k

，那么祖先节点

t_1,t_2,t_4,t_8

都需要

+k

更新(因为

t

表示前缀和)，此时我们就可以用

lowbit

操作实现。

代码

CPP

int add_lacatre(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i)) t[i]+=k;
}

有了基本的思路，那我们就可以直接上代码了。

模版代码

CPP

#include <vector>
using namespace std;

class FenwickTree {
private:
    vector<int> tree; // 树状数组
    int n; // 数组大小（从1到n）

    // 计算 lowbit: x & -x
    int lowbit(int x) {
        return x & -x;
    }

public:
    // 构造函数，初始化大小为 n+1（索引从1开始使用）
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}

    // 在位置 i 上增加 delta（单点更新）
    void update(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += lowbit(i); // 向上更新父节点
        }
    }

    // 查询前缀和 [1, i]（前缀查询）
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i); // 向左上移动到前一个区间
        }
        return sum;
    }

    // 查询区间和 [l, r]（区间查询）
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }

    // 获取原数组位置 i 的值（单点查询）
    // 注意：这不是树状数组的高效用法，仅用于调试或特殊需求
    int get(int i) {
        return rangeQuery(i, i);
    }
};

关键函数详解

1. lowbit(int x)

CPP

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

功能：计算数字二进制表示中最低位的 1 所代表的值
原理：利用补码表示，-x 是 x 的按位取反加 1

2. update(int i, int delta)

CPP

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i); // 移动到父节点
    }
}

功能：在位置 i 增加 delta

过程：

更新当前节点

tree_i

通过

i += lowbit(i)

找到父节点

重复直到超出数组范围

3. query(int i)

CPP

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i); // 移动到前一个区间
    }
    return sum;
}

功能：查询前缀和 $[1, i]$

过程：

累加当前节点

tree[i]

通过

i -= lowbit(i)

移动到前一个区间

重复直到索引为

0

到此结束。。。

文章操作