一维动态前缀和（单修区查）
一维动态前缀和（单修区查）
树状数组（Binary Indexed Tree 或 Fenwick Tree）是一种支持单点修改和区间查询的数据结构。
它能在 的时间复杂度内完成修改和查询操作，是实现动态前缀和的理想选择。
基本概念
树状数组的核心思想是：
- 将数组分成多个不同大小的块
- 每个块存储一定范围内的元素和
- 通过二进制特性快速定位和更新
- 支持动态修改的同时保持较快的查询速度
实现方式
树状数组的关键操作：
- lowbit：获取二进制中最低位的1
- update：单点修改
- query：查询前缀和
- rangeSum：区间查询
基本实现
class BIT {
private:
vector<int> tree;
int n;
int lowbit(int x) {
return x & (-x);
}
public:
BIT(int size) : n(size) {
tree.resize(n + 1);
}
void update(int idx, int delta) {
while (idx <= n) {
tree[idx] += delta;
idx += lowbit(idx);
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
int rangeSum(int left, int right) {
return query(right) - query(left - 1);
}
};
class BIT {
private int[] tree;
private int n;
public BIT(int size) {
n = size;
tree = new int[n + 1];
}
private int lowbit(int x) {
return x & (-x);
}
public void update(int idx, int delta) {
while (idx <= n) {
tree[idx] += delta;
idx += lowbit(idx);
}
}
public int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
public int rangeSum(int left, int right) {
return query(right) - query(left - 1);
}
}
class BIT:
def __init__(self, size):
self.n = size
self.tree = [0] * (size + 1)
def lowbit(self, x):
return x & (-x)
def update(self, idx, delta):
while idx <= self.n:
self.tree[idx] += delta
idx += self.lowbit(idx)
def query(self, idx):
total = 0
while idx > 0:
total += self.tree[idx]
idx -= self.lowbit(idx)
return total
def range_sum(self, left, right):
return self.query(right) - self.query(left - 1)
应用场景
树状数组在很多问题中都有应用：
- 动态区间和查询
- 逆序对计数
- 动态排名统计
- 二维区域和查询
- 区间最值查询（需要修改）
示例：区间和的个数
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
vector<long long> sums(n + 1, 0);
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
set<long long> allNums;
for (long long sum : sums) {
allNums.insert(sum);
allNums.insert(sum - lower);
allNums.insert(sum - upper);
}
// 离散化
map<long long, int> ranks;
int rank = 0;
for (long long num : allNums) {
ranks[num] = ++rank;
}
int result = 0;
BIT bit(ranks.size());
for (long long sum : sums) {
result += bit.rangeSum(ranks[sum - upper], ranks[sum - lower]);
bit.update(ranks[sum], 1);
}
return result;
}
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
TreeSet<Long> allNums = new TreeSet<>();
for (long sum : sums) {
allNums.add(sum);
allNums.add(sum - lower);
allNums.add(sum - upper);
}
// 离散化
Map<Long, Integer> ranks = new HashMap<>();
int rank = 0;
for (long num : allNums) {
ranks.put(num, ++rank);
}
int result = 0;
BIT bit = new BIT(ranks.size());
for (long sum : sums) {
result += bit.rangeSum(ranks.get(sum - upper), ranks.get(sum - lower));
bit.update(ranks.get(sum), 1);
}
return result;
}
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
n = len(nums)
sums = [0] * (n + 1)
for i in range(n):
sums[i + 1] = sums[i] + nums[i]
# 收集所有可能的数值
all_nums = set()
for sum_val in sums:
all_nums.add(sum_val)
all_nums.add(sum_val - lower)
all_nums.add(sum_val - upper)
# 离散化
ranks = {num: rank for rank, num in enumerate(sorted(all_nums), 1)}
result = 0
bit = BIT(len(ranks))
for sum_val in sums:
result += bit.range_sum(ranks[sum_val - upper], ranks[sum_val - lower])
bit.update(ranks[sum_val], 1)
return result
时间复杂度
- 初始化：
- 单点修改：
- 区间查询：
- 空间复杂度：
树状数组 vs 线段树
优点：
- 实现简单，代码量少
- 常数较小，实际运行更快
- 空间占用更少
缺点：
- 功能相对有限
- 不支持区间修改（需要额外技巧）
- 不如线段树灵活
注意事项
- 树状数组下标从1开始
- 注意整数溢出问题
- 更新操作注意增量值
- 区间查询时注意边界
练习建议
- 实现基本的树状数组操作
- 解决区间和相关问题
- 尝试二维树状数组
- 练习树状数组的应用场景
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
