数组]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);}
};
更多推荐
[树状数组]leetcode307:区域和检索 - 数组可修改(medium)
发布评论