C++实现树状数组算法 |21xrx.com

C++实现树状数组算法

2023-07-04 16:05:58 深夜i -- --

C++ 树状数组算法数据结构实现

树状数组（Fenwick Tree）是一种数据结构，用于支持动态单点修改和前缀查询的高效实现。它通过巧妙地利用二进制的性质，在空间和时间方面都比较优秀。

C++是一种面向对象的高级编程语言，它的语法简洁灵活，可读性较高，因此在算法竞赛等领域备受推崇。下面我们使用C++来实现树状数组算法。

首先，我们需要定义一个int类型的数组bit，代表树状数组。其大小设为数组a的大小加一，因为树状数组是从下标1开始的。

int bit[MAX_N+1];

其次，我们需要实现两个主要的操作：单点修改和前缀查询。其中单点修改是指将a[i]的值加上delta，可以通过不断向上爬树，并更新所有影响到的子树来完成。前缀查询是指查询从1到i的所有元素之和，同样是通过向上爬树来实现。

void add(int i, int delta) {

while (i <= n) {

bit[i] += delta;

i += i & -i;

}

int sum(int i) {

int res = 0;

while (i > 0) {

res += bit[i];

i -= i & -i;

}

return res;

}

最后，我们可以将这些操作封装在一个类中，方便进行调用和管理。类中的成员变量包括原始数组a、树状数组bit以及数组a的大小n。成员函数包括构造函数、单点修改函数add、前缀查询函数sum等。

class FenwickTree {

public:

FenwickTree(vector & a) {

n = a.size();

bit.resize(n+1);

for (int i = 0; i < n; i++) {

add(i+1, a[i]);

}

void add(int i, int delta) {

while (i <= n) {

bit[i] += delta;

i += i & -i;

}

int sum(int i) {

int res = 0;

while (i > 0) {

res += bit[i];

i -= i & -i;

}

return res;

}

private:

vector bit;

int n;

};

综上所述，C++实现树状数组算法的过程不仅可以锻炼编程能力，也能够更好地理解树状数组的本质，是一项非常有意义的任务。

上一篇: idea打包java可执行jar包

下一篇: C++ 入门指南：从入门到放弃

评论区

()

相似文章