# 树状数组¶

## 1、什么是树状数组¶

1. 修改一个点求一个区间
2. 修改一个区间求一个点
3. 求逆序列对

1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000


C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];


C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i];   //k为i的二进制中从最低位到高位连续零的长度

例如：
1， 没有0，只保存1
2，10，有1个0，保存当前值和这个0变成1的组合，也就是1
3， 没有0，只保存1
4，100，保存4和 00 的组合，也就是1，2，3


第一步：获取7中和值
111

111 - 1 = 110

110 - 10 = 100


第一步：更新3
11

11 + 1 = 100

100 + 100 = 1000


## 2、树状数组实现¶

class BinaryIndexTree:
def __init__(self, nums):
"""
:type nums: List[int]
"""

self.nums = nums
self.buff = [0] * (len(nums) + 1)
for i in range(1, len(nums) + 1):
temp = nums[i - 1]
while i < (len(nums) + 1):
self.buff[i] += temp
i += i & (-i)

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: void
"""
index = i + 1
diff = val - self.nums[i]
while index < len(self.buff):
self.buff[index] += diff
index += index & (-index)

self.nums[i] = val

def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.getSum(j + 1) - self.getSum(i)

def getSum(self, index):
res = 0

while index > 0:
res += self.buff[index]
index -= index & (-index)

return res

a = [5, 4, 3, 2, 1, 5, 7, 7, 9]
seg = BinaryIndexTree(a)
print(seg.buff)

# assert query
for left in range(9):
for right in range(left, 9):
assert sum(a[left:right + 1]) == seg.sumRange(left, right)

[0, 5, 9, 3, 14, 1, 6, 7, 34, 9]