朋友喊我先刷每日一题，对我来说有点难，先试试看……

307. 区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值

另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象

void update(int index, int val) 将 nums[index] 的值 更新 为 val

int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

即：

update(idx, delta)：将num加到位置idx的数字上。

prefixSum(idx)：求从数组第一个位置到第idx（含idx）个位置所有数字的和。

rangeSum(from_idx, to_idx)：求从数组第from_idx个位置到第to_idx个位置的所有数字的和

这道题其实就是实现前缀数组。

用O（n）的时间来创建前缀数组，

该数组中的第i个位置保存原数组中前i个元素的和，则对于上述每一个操作，我们有：

update(idx, delta)：更新操作需要更新cumulative sum数组中每一个受此更新影响的前缀和，即从idx其到最后一个位置的前缀和。该操作为O(n)时间复杂度。

prefixSum(idx)：直接返回cumulativeSum[idx + 1]即可。该操作为O(1)时间复杂度。

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

需要的数据结构：

Binary Indexed Tree 树状数组或二叉索引树

Binary Indexed Tree事实上是将根据数字的二进制表示来对数组中的元素进行逻辑上的分层存储。

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

也就是先求2^3个数之和，再求2^2个数之和，再求2^0个数之和。

如何存储？

①在第一行中，从第一个开始，没有截断，因此依次增加2^n个。1增加2^0，到2，2增加2^1，到4，4增加2^2到8，由于8增加2^3超过14个，则第一行结束。

②在第二行中，因为1，2都已经有了，3截断到3，所以只有3；

5截断到7，因此5增加2^0，到6，6增加2^1到8超过8，结束;

9截断到14，因此9增加2^0，到10，10增加2^1，到12，12增加2^2到16超过14，结束;

③在第三行中，7截断到7，结束。

11截断到11，结束。

13截断到14，13增加2^0到14，结束。

1.求和

因此：

prefixSum(13) = prefixSum(0b00001101)

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

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

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

如何求一个二进制数去掉末尾1得到的值？

x = 13 = 0b00001101 

-x = -13 = 0b11110011 

x & (-x) = 0b00000001 

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

2.更新数组内的值：

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

x = 5 = 0b00000101

-x = -5 = 0b11111011

x & (-x) = 0b00000001

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

3.树状数组的建立：

我们需初始化一个全为0的数组，并对原数组中的每一个位置对应的数字调用一次update(i, delta)操作即可。这是一个O(nlogn)的建立过程。

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

以下为题解(参考了大佬的，我确实不太行orz但是我相信注释足够详细了，大家应该都可以看懂~)：

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

   def __init__(self, nums: List[int]):
       self.tree=[0]+nums #从1开始标下标
       for i in range(1,len(self.tree)):
           j=i+self.lowbit(i)
           if j<len(self.tree):  #对所有这个数出现后需要update的数进行update
               self.tree[j] += self.tree[i]

   def preSum(self,index:int)-> int:
       #写一个函数获得1到index的和
       i=index+1 #index表示该数在nums中的位置，由于下标右移1，所以用i存放现在tree数组的位置
       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位置在前缀数组中的值
       delta=val-pre_vel #该数字被更新之后，所有前缀组中相关的数都应该随之加上或减去相同的值
       i=index+1 #调用sumRange时，又调用preSum，这时候的子函数里面的index是正确对应的，但是update函数的index是对应nums数组的，而不是tree数组的
       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之间的数组和，即用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)