Leetcode307. 区域和检索 - 数组可修改的三种解法

喜欢ヅ旅行 2023-01-08 08:22 72阅读 0赞

# 区域和检索 - 数组可修改的三种解法 #

**注意:因为暴力求解时间复杂度太高,我们在此不在考虑**

## 方法一、分块求解 ##

我们可以将数组分成sqrt(n)块,其中n是数组的长度,然后进行求解  
代码如下:

class NumArray {
        
        int[] bitSum;
        int[] nums;
        int len;
        //尝试使用sqrt分解求解此问题
        public NumArray(int[] nums) {
        
            this.nums=nums;
            //开始进行分块
            double tem=Math.sqrt(nums.length);
            len=(int) Math.ceil(tem);
            bitSum=new int[len];
            for(int i=0;i<nums.length;i++) {
        
            	bitSum[i/len]+=nums[i];
            }
        }
        
        public void update(int index, int val) {
        
        	int bitIndex=index/len;
        	int dif=nums[index]-val;
        	this.bitSum[bitIndex]-=dif;
        	nums[index]=val;
        }
        
        public int sumRange(int left, int right) {
        
        	int ret=0;
        	if(right-left+1<2*len) {
        
        		for(int i=left;i<=right;i++) {
        
        			ret+=nums[i];
        		}
        	}
        	else {
        
        		while(left%len!=0) {
        
        			ret+=nums[left];
        			left++;
        		}
        		ret+=bitSum[left/len];
        		left+=len;
        		
        		if(right-left+1==len) ret+=bitSum[left/len];
        		else {
        
        			for(int i=left;i<=right;i++) {
        
        				ret+=nums[i];
        			}
        		}
        	}
        	return ret;
        }
    }

## 方法二、线段树求解 ##

我们可以使用简化的线段树,通过数组去模拟二叉树进行求解  
代码如下:(注意我们构造的线段树是从数组标号1开始的以使得i的孩子为2*i和2*i+1)

class NumArray {
        
        int[] tree;
        int n;
        //尝试使用线段树求解此题目
        public NumArray(int[] nums) {
        
            n=nums.length;
            tree=new int[2*n];
            //从底向上构造线段树
            for(int i=n,j=0;i<2*n;i++,j++) {
        
            	tree[i]=nums[j];
            }
            for(int i=n-1;i>0;i--) {
        
            	tree[i]=tree[2*i]+tree[2*i+1];
            }
        }
        
        public void update(int index, int val) {
        
        	//从底向上更新线段树
        	index=index+tree.length/2;
        	tree[index]=val;
            //System.out.println(index);
        	while(index>0) {
        
                int l=index;
                int r=index;
                if(index%2==0) r++;
                else l--;
                index/=2;
        		tree[index]=tree[l]+tree[r];
            	//index/=2;
        	}
        }
        
        public int sumRange(int left, int right) {
        
        	//开始进行求和
        	int sum=0;
            left+=tree.length/2;
            right+=tree.length/2;
        	while(left<=right) {
        
        		if(left%2==1) {
        
        			sum+=tree[left];
        			left++;
        		}
        		if(right%2==0) {
        
        			sum+=tree[right];
        			right--;
        		}
        		left/=2;
        		right/=2;
        	}
        	return sum;
        }
    
    }

## 方法三、使用树状数组求解此问题 ##

此结构也是模拟二分的方法

class NumArray {
        
        //尝试使用树状数组解决此问题
        private int n;
        private int[] treeNums;
        private int[] nums;
        public NumArray(int[] nums) {
        
        	n=nums.length;
        	int[] preSum=new int[n+1];
            treeNums=new int[n+1];
            this.nums=nums;
            for(int i=1;i<=n;i++) {
        
            	//使用前缀和的方法构造树状数组
            	preSum[i]+=preSum[i-1]+nums[i-1];
            	treeNums[i]=preSum[i]-preSum[i-(i&(-i))];
            }
        }
        
        public void update(int index, int val) {
        
        	int dif=nums[index]-val;
        	nums[index]=val;
            int s=index+1;
        	for(;s<=n;s+=(s&(-s))) {
        
        		treeNums[s]-=dif;
            }
        }
        
        public int sumRange(int left, int right) {
        
        	//求right的前缀和
            int s=right+1;
        	int sum1=0,sum2=0;
        	for(;s>0;s-=(s&(-s))) {
        
        		sum1+=treeNums[s];
        	}
        	s=left;
        	for(;s>0;s-=(s&(-s))) {
        
        		sum2+=treeNums[s];
        	}
        	return sum1-sum2;
        }
    }