当前位置：首页 > news >正文

307.区域和检索

news 来源：原创 2024/5/21 0:31:06

题目来源：

leetcode题目，网址：307. 区域和检索 - 数组可修改 - 力扣（LeetCode）

解题思路：

线段树，以二叉树的形式存储部分区间之和及总和。

解题代码：

class NumArray {
private:vector<int> segment;int n;void buildSegment(int pos,int start,int end,vector<int>& nums){if(start==end){segment[pos]=nums[start];return ;}int mid=start+(end-start)/2;    //一般元素buildSegment(pos*2+1,start,mid,nums);       //前半段的和buildSegment(pos*2+2,mid+1,end,nums);       //后半段的和segment[pos]=segment[pos*2+1]+segment[pos*2+2];return ;}void change(int posNow,int startPos,int endPos,int targetPos,int targetVal){if(startPos==endPos){segment[posNow]=targetVal;return ;}int mid=startPos+(endPos-startPos)/2;if(targetPos<=mid){change(2*posNow+1,startPos,mid,targetPos,targetVal);}else{change(2*posNow+2,mid+1,endPos,targetPos,targetVal);}segment[posNow]=segment[2*posNow+1]+segment[2*posNow+2];}int getSum(int posNow,int startPos,int endPos,int left,int right){if(left==startPos && right==endPos){return segment[posNow];}int mid=startPos+(endPos-startPos)/2;if(right<=mid){return getSum(posNow*2+1,startPos,mid,left,right);}else if(left>mid){return getSum(posNow*2+2,mid+1,endPos,left,right);}else{return getSum(posNow*2+1,startPos,mid,left,mid)+getSum(posNow*2+2,mid+1,endPos,mid+1,right);}}
public:NumArray(vector<int>& nums) {n=nums.size();vector<int> newSeg(4*nums.size());  //元素个数不会超过2*nums.size()-1segment=newSeg;buildSegment(0,0,nums.size()-1,nums);/*     for(int i=0;i<segment.size();i++){cout<<segment[i]<<" ";}cout<<endl;*/}void update(int index, int val) {change(0,0,n-1,index,val);/*     cout<<"update "<<index<<" "<<val<<endl;for(int i=0;i<segment.size();i++){cout<<segment[i]<<" ";}cout<<"end"<<endl;*/}int sumRange(int left, int right) {return getSum(0,0,n-1,left,right);}
};/*** Your NumArray object will be instantiated and called as such:* NumArray* obj = new NumArray(nums);* obj->update(index,val);* int param_2 = obj->sumRange(left,right);*/

总结：

没做出来，看官方题解的。

官方题解给出了三种解法。第一种是通过分块降低时间复杂度。第二种是线段树。第三种是树状数组。