Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.Example:
Given nums = [1, 3, 5]sumRange(0, 2) -> 9update(1, 2)sumRange(0, 2) -> 8Note:
The array is only modifiable by the update function.You may assume the number of calls to update and sumRange function is distributed evenly.这里的提示标签是: segment tree; binary indexed tree
自己扫盲了一下树状数组(BIT,binary indexed tree)。
数组A下标通常从0开始，而树状数组的有效下标是从1开始。树状数组中元素在树型结构中的位置是根据数组下标的末尾0的个数r确定，
是2^r个nums的和。定义每一个元素BITT[i]的值等于A[i-2^r + 1] + ... + A[i]，即T[i]表示共2^r个元素的部分累加和，或者说T[i]元素管辖区段
从i开始往前推2^r个元素。2^r的计算方法很简单，就是i & (-i)，原理是利用负数补码等于相应正数值取反加一。
转载出处：点击打开链接
更详细的资源：点击打开链接 点击打开链接
新闻热点
疑难解答
