§05 线性结构

树状数组 Fenwick Tree

lowbit 跳跃:单点更新与前缀和都是 O(log n)——比线段树轻量十倍。

树状数组 Fenwick Tree

第 01 / 12 步

初始数组 3, 2, 5, 7, 1, 4, 6, 8。tree 数组 1-based，tree[i] 管辖区间 [i-lowbit(i)+1, i]。比较 0 · 交换 0

伪代码


				
					
					1
					// lowbit(x) = x & (-x)
				
			
				
					
					2
					update(i, delta):
				
			
				
					
					3
					  while i <= n: tree[i] += delta; i += lowbit(i)
				
			
				
					
					4
					query(i):  // 前缀和 [1..i]
				
			
				
					
					5
					  sum = 0
				
			
				
					
					6
					  while i > 0: sum += tree[i]; i -= lowbit(i)

01 / 12

速度