Fenwick Tree

树状数组，适合用于：

动态维护前缀和

1
a=[1,3,5,7,9]

不断有操作：

1
2
修改 a[3]+=10
查询 a[1]+...+a[4]

Fenwick：

  • 修改 O(log n)
  • 查询 O(log n)

统计“前面有多少个”

1
3 1 4 2

问每个数左边有多少比它小。

从左到右：

1
2
3
4
5
6
7
8
9
10
11
12
13
3:
左边没有

1:
左边比它小的数量=0

4:
左边有1,3
答案=2

2:
左边有1
答案=1

这里需要：

  • 插入一个数
  • 查询小于它的数量

维护频率表（最常用）

数字范围：

1
1~100000

维护数字出现次数。

比如：

1
2
cnt[5]=3
cnt[8]=2

操作：

加入一个数字：

1
add(x,+1)

删除：

1
add(x,-1)

查询：

1
1~x出现多少个

代码理解

初始化

1
2
3
4
class Fenwick:
    def __init__(self,n):
        self.n=n
        self.tree=[0]*(n+1)

单点修改

1
2
3
4
def add(self,i,x):
    while i<=self.n:
        self.tree[i]+=x
        i+=i&-i

“修改往后跳”

前缀查询

1
2
3
4
5
6
def sum(self,i):
    ans=0
    while i:
        ans+=self.tree[i]
        i-=i&-i
    return ans

“查询往前跳”