利用lowbit来划分每个元素控制的区间，保证可以在logn时间内完成单点修改和区间求和。
# 注意，树状数组的下标从1开始，所以tree要在开头补一个0 # 初始为0，用原数组中的每个数去更新树状数组就完成建树的过程 class BIT: def __init__(self, n): self.n = n # n为原数组的长度 self.tree = [0] * (n + 1) @staticmethod def lowbit(x): return x & (-x) def query(self, idx): ret = 0 while idx > 0: ret += self.tree[idx] idx -= BIT.lowbit(idx) return ret def update(self, idx, v): # v是更新前后的插值 while idx <= self.n: self.tree[idx] += v idx += BIT.lowbit(idx) nums = list(range(10)) bit = BIT(len(nums)) for i in range(1, len(nums)): # 建树 bit.update(i, nums[i]) print(bit.query(5))利用树状数组求逆序对的个数：
首先来看用频次数组怎么求。求一个数组逆序对的个数等价于对于这个数组中的每一个元素，在它的左边有多少个比它大的元素。假设数组元素满足 0 <= x <= maxn，我们只要依次把每个数组元素放入频次数组中，再遍历 cnt[x+1] 到 cnt[maxn] 来统计个数即可。这样做的问题就是每次都要访问一遍 cnt[x+1] 到 cnt[maxn] ，时间复杂度为 O(n * maxn)，可以用树状数组来改善这个问题。
刚才说到要遍历 cnt[x+1] 到 cnt[maxn] 来统计个数，也就相当于遍历 cnt[1] 到 cnt[x] 来统计个数再用 n 减去它。其实就是求前 x 项的和，自然就可以用树状数组来实现。初始化为0，第 k 次单点修改后求出前 k 项的和即可。n次单点修改和区间求和的复杂度为 O(n * logn)。
res = 0 for i, x in enumerate(nums): update(x, 1) res += i+1 - query(x) print(res)当maxn过大时，要离散化。也就是先排序，再在新数组中依次查找原数组中每个元素的位置。（O(n*logn)）
sorted_nums = sorted(nums) new_nums = [None] * len(nums) for i in range(len(nums)): new_nums[i] = sorted_nums.index(nums[i])+1 # index相当于lower_bound