问题
给定一个序列a,需要对这个序列进行两种操作:
- 计算序列a中任意两个位置之间所有元素的和;
- 能够更改序列a中任意一个位置元素的值;
现存解法
方法一:暴力求和。那么操作1的时间复杂度为O(n)
,操作2的时间复杂度为O(1)
;
方法二:使用前缀和数组。那么操作1的时间复杂度为O(1)
,操作2的时间复杂度为O(n)
;
那么有没有可能存在一种算法,使得以上两种操作的时间复杂度都是O(nlogn)
?
——树状数组(BIT - binary indexed tree)
结构示例
解析:
以上结构分为两个数组,原始序列a和辅助序列c;
主要理解以下3个操作及其概念:
- lowbit计算;
- 计算c父节点;
- 计算c左邻节点;
TODO