树状数组C/C++实现
目录
树状数组简介
基本原理
特点
核心操作
算法实现
单点更新
区间求和
应用场景
树状数组的主要操作
C/C++实现
1. 单点更新
2. 区间求和
树状数组简介
树状数组，也称为二叉索引树或Fenwick树，是一种用于处理数据序列的高效数据结构，特别适合于区间查询和更新操作。它通过构建一个类似二叉树的结构来减少查询和更新的时间复杂度，使得单点更新和区间查询的时间复杂度都降低到 O(\log n)。
树状数组（Binary Indexed Tree，简称BIT或Fenwick Tree）是一种用于高效处理数据序列的算法数据结构。它能够支持两个主要操作：单点更新和区间求和，这两个操作的时间复杂度都能达到 O(\log n)，其中 n 是数据序列的长度。树状数组非常适合处理那些需要频繁更新和查询区间和的问题。
基本原理
树状数组的核心思想是将数据序列映射到一棵二叉树中，这棵树并不是普通的二叉树，而是一棵完全二叉树，并且每个节点的值表示从该节点到叶子节点的区间和。通过这棵二叉树，我们可以快速地计算出任意区间的和。
特点
1. 高效性：树状数组可以快速地进行区间求和和单点更新操作。
2. 空间优化：相比于线段树，树状数组的空间复杂度更低，只需要一个大小为 n+1的数组。
3. 简单性：相比于线段树，树状数组的实现更为简单。
核心操作
1. 单点更新：将序列中的第 i 个元素增加 Delta。
2. 区间求和：计算序列中从第 l 个元素到第 r 个元素的和。
算法实现
树状数组的实现依赖于一个核心技巧：对于数组中的任意位置 i，可以通过 i的二进制表示找到所有大于 i 的最小二进制单位（即找到所有大于 i 的 2^k，其中 k 是 i 的二进制表示中最低位的1）。
单点更新
对于数组中的第 i 个元素，要增加 Delta，就需要从 i 开始，逐个加上 Delta，直到 n+1。
区间求和
对于求区间 [l, r] 的和，可以先求 1 到 r 的和，然后减去 1 到 l-1 的和。
应用场景
树状数组在算法竞赛和实际应用中非常常见，例如：
1. 动态逆序对：在给定一个数组，每次可以增加或减少某个元素的值，求最终数组中逆序对的数量。
2. 区间修改：在某些问题中，需要对数组的某个区间进行修改，然后查询修改后的数组信息。
3. 图的最短路径问题：在某些图算法中，树状数组可以用来优化查询和更新操作。
树状数组是一种非常强大的数据结构，理解并掌握它对于解决复杂问题非常有帮助。
树状数组的主要操作
1. 单点更新：对序列中的某个元素进行更新。
2. 区间求和：计算序列中某一段区间的元素和。
C/C++实现
1. 单点更新
单点更新操作是将序列中索引为 i 的元素增加一个值 delta。
#include <iostream>
#include <vector>using namespace std;class BIT {
private:vector<int> tree;int n;int lowbit(int x) {return x & (-x);}public:BIT(int size) : n(size), tree(size + 1, 0) {}void update(int i, int delta) {while (i <= n) {tree[i] += delta;i += lowbit(i);}}
};2. 区间求和
区间求和操作是计算序列中从索引 `l` 到 `r` 的元素和。
int query(int r) {int sum = 0;while (r > 0) {sum += tree[r];r -= lowbit(r);}return sum;}int range_query(int l, int r) {return query(r) - query(l - 1);}
};int main() {BIT bit(10);bit.update(3, 5);bit.update(4, 3);cout << "Sum from 1 to 4: " << bit.range_query(1, 4) << endl; // 输出 8return 0;
}树状数组是一种非常实用的数据结构，特别适用于处理区间更新和查询问题。通过上述代码，你可以在C/C++中实现树状数组的基本操作。这种数据结构在算法竞赛和实际应用中都非常有用，例如在处理动态规划问题中的优化、图的最短路径问题等。
希望这篇博客能帮助大家理解并实现树状数组。如果你有任何问题或需要进一步的解释，请随时私信我。