深入分析树状数组结构化技术

引言

树状数组的目的：快速求前缀和，修改某一个数

普通数组采用高效的方法计算前缀和，并能在常数时间内进行单个元素的更新；树状数组则通过高效的计算方式实现前缀和查询，并支持在对数时间内完成单个元素的更新。

树状数组的示意图

树状数组的主要特点在于基于二进制性质实现了高效的查询与更新操作

主要由三个核心的函数构成

函数 lowbit(x)

主要是为了找到最低1位，因此lowbit(x) = x&-x

查询函数 query(x)

计算区间[1, x]内的总和。请注意从数字1开始。
在这一阶段，请将与变量x相关的各个位置上的数值相加。
具体来说，在x对应的二进制表示中，
那些为1的位置会被考虑进去。

    def query(x):
    	res = 0
    	while x>0:
    		res += tree[x]
    		x -= lowbit(x)
    	return res

添加函数 add(x, value)

对该值进行修改的同时需要修改与其相关的全部位置