朋友喊我先刷每日一題，對我來說有點(diǎn)難，先試試看……

307. 區(qū)域和檢索 - 數(shù)組可修改

給你一個數(shù)組 nums ，請你完成兩類查詢。

其中一類查詢要求 更新 數(shù)組 nums 下標(biāo)對應(yīng)的值

另一類查詢要求返回數(shù)組 nums 中索引 left 和索引 right 之間（ 包含 ）的nums元素的 和 ，其中 left <= right

實(shí)現(xiàn) NumArray 類：

NumArray(int[] nums) 用整數(shù)數(shù)組 nums 初始化對象

void update(int index, int val) 將 nums[index] 的值 更新 為 val

int sumRange(int left, int right) 返回數(shù)組 nums 中索引 left 和索引 right 之間（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

即：

update(idx, delta)：將num加到位置idx的數(shù)字上。

prefixSum(idx)：求從數(shù)組第一個位置到第idx（含idx）個位置所有數(shù)字的和。

rangeSum(from_idx, to_idx)：求從數(shù)組第from_idx個位置到第to_idx個位置的所有數(shù)字的和

這道題其實(shí)就是實(shí)現(xiàn)前綴數(shù)組。

用O（n）的時間來創(chuàng)建前綴數(shù)組，

該數(shù)組中的第i個位置保存原數(shù)組中前i個元素的和，則對于上述每一個操作，我們有：

update(idx, delta)：更新操作需要更新cumulative sum數(shù)組中每一個受此更新影響的前綴和，即從idx其到最后一個位置的前綴和。該操作為O(n)時間復(fù)雜度。

prefixSum(idx)：直接返回cumulativeSum[idx + 1]即可。該操作為O(1)時間復(fù)雜度。

rangeSum(from_idx, to_idx)：直接返回cumulativeSum[to_idx + 1] - cumulativeSum[from_idx]即可。該操作為O(1)操作。

需要的數(shù)據(jù)結(jié)構(gòu)：

Binary Indexed Tree?樹狀數(shù)組或二叉索引樹

Binary Indexed Tree事實(shí)上是將根據(jù)數(shù)字的二進(jìn)制表示來對數(shù)組中的元素進(jìn)行邏輯上的分層存儲。

eg：prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13)

也就是先求2^3個數(shù)之和，再求2^2個數(shù)之和，再求2^0個數(shù)之和。

如何存儲？

①在第一行中，從第一個開始，沒有截斷，因此依次增加2^n個。1增加2^0，到2，2增加2^1，到4，4增加2^2到8，由于8增加2^3超過14個，則第一行結(jié)束。

②在第二行中，因為1，2都已經(jīng)有了，3截斷到3，所以只有3；

5截斷到7，因此5增加2^0，到6，6增加2^1到8超過8，結(jié)束;

9截斷到14，因此9增加2^0，到10，10增加2^1，到12，12增加2^2到16超過14，結(jié)束;

③在第三行中，7截斷到7，結(jié)束。

11截斷到11，結(jié)束。

13截斷到14，13增加2^0到14，結(jié)束。

1.求和

因此：

prefixSum(13) = prefixSum(0b00001101)

= BIT[13] + BIT[12] + BIT[8]

= BIT[0b00001101] + BIT[0b00001100] + BIT[0b00001000]

13->12->8，依次截去末尾的最后一個1

如何求一個二進(jìn)制數(shù)去掉末尾1得到的值？

x = 13 = 0b00001101?

-x = -13 = 0b11110011?

x & (-x) = 0b00000001?

x - (x & (-x)) = 0b00001100

2.更新數(shù)組內(nèi)的值：

每次都加上最后一個1代表的值

x = 5 = 0b00000101

-x = -5 = 0b11111011

x & (-x) = 0b00000001

x + (x & (-x)) = 0b00000110

3.樹狀數(shù)組的建立：

我們需初始化一個全為0的數(shù)組，并對原數(shù)組中的每一個位置對應(yīng)的數(shù)字調(diào)用一次update(i, delta)操作即可。這是一個O(nlogn)的建立過程。

---------------------------------------------------------------------------

以下為題解(參考了大佬的，我確實(shí)不太行orz但是我相信注釋足夠詳細(xì)了，大家應(yīng)該都可以看懂~)：

class NumArray:
? ?def lowbit(self,x:int)->int:
? ? ? ?return x&(-x)

? ?def __init__(self, nums: List[int]):
? ? ? ?self.tree=[0]+nums #從1開始標(biāo)下標(biāo)
? ? ? ?for i in range(1,len(self.tree)):
? ? ? ? ? ?j=i+self.lowbit(i)
? ? ? ? ? ?if j<len(self.tree): ?#對所有這個數(shù)出現(xiàn)后需要update的數(shù)進(jìn)行update
? ? ? ? ? ? ? ?self.tree[j] += self.tree[i]

? ?def preSum(self,index:int)-> int:
? ? ? ?#寫一個函數(shù)獲得1到index的和
? ? ? ?i=index+1 #index表示該數(shù)在nums中的位置，由于下標(biāo)右移1，所以用i存放現(xiàn)在tree數(shù)組的位置
? ? ? ?summ=0
? ? ? ?while i:
? ? ? ? ? ?summ += self.tree[i]
? ? ? ? ? ?i-=self.lowbit(i) #求和
? ? ? ?return summ

? ?def update(self, index: int, val: int) -> None:
? ? ? ?pre_vel=self.sumRange(index,index) #pre_vel代表index位置在前綴數(shù)組中的值
? ? ? ?delta=val-pre_vel #該數(shù)字被更新之后，所有前綴組中相關(guān)的數(shù)都應(yīng)該隨之加上或減去相同的值
? ? ? ?i=index+1 #調(diào)用sumRange時，又調(diào)用preSum，這時候的子函數(shù)里面的index是正確對應(yīng)的，但是update函數(shù)的index是對應(yīng)nums數(shù)組的，而不是tree數(shù)組的
? ? ? ?while i<len(self.tree):
? ? ? ? ? ?self.tree[i] +=delta
? ? ? ? ? ?i+=self.lowbit(i)


? ?def sumRange(self, left: int, right: int) -> int:
? ? ? ?return self.preSum(right)-self.preSum(left-1)
? ?#求left到right之間的數(shù)組和，即用right的前綴和減去left的前綴和


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)