[树状数组]leetcode307：区域和检索 - 数组可修改(medium)

数组]leetcode307：区域和检索 - 数组可修改(medium)"/>

[树状数组]leetcode307：区域和检索 - 数组可修改(medium)

题目：

题解：

• 题解1：暴力法
• 题解2：树状数组

题解1：

class NumArray{
private:vector<int> nums;
public:NumArray(vector<int>& nums) {this->nums=nums;}void update(int i, int val) {nums[i]=val;}int sumRange(int i, int j) {return accumulate(nums.begin()+i,nums.begin()+j+1,0);}
};

题解2：

class NumArray{
private://原始数组每个元素对应的下标+1就是数组数组中的下标了，所以树状数组比原始数组多一个，下标0在原始数组中没有对应的，设为0vector<int> nums;vector<int> C;
public:int lowbit(int x){return x&(-x);}void add(int i,int val){//i表示原始数组中的下标，i+1表示树状数组中的下标for(int k=i+1;k<=nums.size();k+=lowbit(k)){C[k]+=val;}}int getSum(int i){int sum=0;for(int k=i;k>0;k-=lowbit(k)){//从下标1开始计算sum+=C[k];}return sum;}NumArray(vector<int>& nums):nums(nums) {C.resize(nums.size()+1);//使用add生成树状数组，时间复杂度为O(nlogn)for(int i=0;i<nums.size();++i)add(i,nums[i]);}void update(int i, int val) {//val小于nums[i]，那么下标i的元素值就要变小；反之，变大add(i,val-nums[i]);nums[i]=val;}int sumRange(int i, int j) {//比如调用(0,2)，原始数组中的下标2对应树状数组中的下标3，0不变return getSum(j+1)-getSum(i);}
};