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
自己掃盲了一下樹狀數(shù)組(BIT,binary indexed tree)。
數(shù)組A下標通常從0開始，而樹狀數(shù)組的有效下標是從1開始。樹狀數(shù)組中元素在樹型結(jié)構(gòu)中的位置是根據(jù)數(shù)組下標的末尾0的個數(shù)r確定，
是2^r個nums的和。定義每一個元素BITT[i]的值等于A[i-2^r + 1] + ... + A[i]，即T[i]表示共2^r個元素的部分累加和，或者說T[i]元素管轄區(qū)段
從i開始往前推2^r個元素。2^r的計算方法很簡單，就是i & (-i)，原理是利用負數(shù)補碼等于相應(yīng)正數(shù)值取反加一。
轉(zhuǎn)載出處：點擊打開鏈接
更詳細的資源：點擊打開鏈接 點擊打開鏈接
新聞熱點
疑難解答
