区间树和芬威克树（BIT）如何支持快速范围查询？

Question

IT Interview Practice · Accepted Answer

**区间树**和**芬威克树**（Binary Indexed Tree，BIT）都能在**O(log n)**时间内回答**范围查询**（例如`[l, r]`范围内的求和）和**点更新**，相比之下naive扫描需要O(n)，前缀和数组更新需要O(n)。

## 它们解决的问题

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## 芬威克树（BIT）— 紧凑而优雅

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## 区间树 — 更通用

区间树在二叉树中为每个数组区间存储一个聚合值，支持**任何结合律运算**（求和、最小值、最大值、最大公约数），并且通过懒传播还支持**范围更新**。

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## 比较

| | Fenwick (BIT) | Segment tree |
|---|---|---|
| Query / update | O(log n) | O(log n) |
| Space | O(n) | O(2n) |
| Operations | sums (invertible) | any associative op |
| Range updates | 困难 | 简单 (lazy propagation) |
| Code size | 极小 | 较大 |

## 为什么这很重要

这些结构使"更新一个值，然后查询范围内的聚合值"变得高效——这对竞技编程、分析窗口和区间问题至关重要。

在它们之间的选择是一种权衡：芬威克树代码极小且对求和操作很快，而区间树对最小值/最大值/范围更新工作负载更灵活。

	Fenwick (BIT)	Segment tree
Query / update	O(log n)	O(log n)
Space	O(n)	O(2n)
Operations	sums (invertible)	any associative op
Range updates	困难	简单 (lazy propagation)
Code size	极小	较大

它们解决的问题

芬威克树（BIT）— 紧凑而优雅

区间树 — 更通用

比较

为什么这很重要

相关问题