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

 1 class NumArray {
 2 public:
 3     vector<int> number;
 4     vector<int> sum;
 5     NumArray(vector<int>& nums) {
 6         if(nums.empty()) return ;
 7         sum.push_back(nums[0]);
 8         number.push_back(nums[0]);// number=nums;直接赋值
 9         for(int i=1;i<nums.size();i++){
10             sum.push_back(sum[i-1]+nums[i]);
11             number.push_back(nums[i]);
12         }
13     }
14     
15     void update(int i, int val) {
16         
17         int tmp=number[i];
18         number[i]=val;
19         for(int j=i;j<number.size();j++){
20             sum[j]+=val-tmp;
21         }
22     }
23     
24     int sumRange(int i, int j) {
25         if(i==0) return sum[j];
26         return sum[j]-sum[i-1];
27 
28     }
29 };

 1 class BitTree{//这里面 不需要加public
 2 public:
 3     vector<int> arr;
 4     BitTree(){}
 5     BitTree(vector<int>& nums){
 6         arr.push_back(0);//从1  到 n 存储赋值，下标0 不用 大小n+1个;
 7         for(int i=0;i<nums.size();i++){
 8             arr.push_back(nums[i]);
 9         }
10         for(int i=1;i<arr.size();i++){
11             int j=i+(i&-i);
12             if(j<arr.size()){//最后一个的下标 位 arr.size()-1
13                 arr[j]+=arr[i];//arr[j]=arr[j]+arr[i];
14             }
15         }
16     }
17     void update(int index,int val){//代表 在 index位置上 加上val，之后更新相应位置
18         index+=1;//下标往后移动1位，因为 数据在 1 到n
19         while(index<arr.size()){
20             arr[index]+=val;
21             index=index+(index&-index);
22         }
23     }
24     int prefixSum(int index){//前缀和
25         index+=1;
26         int sum=0;
27         while(index>0){
28             sum+=arr[index];
29             index=index-(index&-index);
30         }
31         return sum;
32     }
33 };
34 
35 class NumArray {
36 public:
37     vector<int> number;//存储原来的值
38     BitTree btree;//树状数组
39     NumArray(vector<int>& nums) {
40         if(nums.empty()) return ;
41         number=nums;
42         btree=BitTree(nums);
43     }
44     
45     void update(int i, int val) {
46         btree.update(i,val-number[i]);//增加的值 是 val-nums[i]
47         number[i]=val;//更新这个位置的值
48     }
49     
50     int sumRange(int i, int j) {
51         //if(i==0) return btree.prefixSum(j);
52         return btree.prefixSum(j)-btree.prefixSum(i-1);
53     }
54 };