303. 区域和检索 - 数组不可变 难度：简单-中等
题目中给的数组的最大长度为10^4,最多调用方法10^4次，每次调用方法最多全部遍历一次数组，因此暴力解法的复杂度小于10^8，可以求解。
1 class NumArray { 2 int[] nums; 3 public NumArray(int[] nums) { 4 this.nums = nums; 5 } 6 7 public int sumRange(int i, int j) { 8 int sum = 0; 9 for(int k=i;k<=j;k++){ 10 sum+=this.nums[k]; 11 } 12 return sum; 13 } 14 } 15 16 /** 17 * Your NumArray object will be instantiated and called as such: 18 * NumArray obj = new NumArray(nums); 19 * int param_1 = obj.sumRange(i,j); 20 */
既然是多次查询，可能存在重复的i和j，创建一个HashMap，存储已经找到的部分和，在找部分和时，先看HashMap是否已经存在，如果不存在，才去遍历数组。
1 class NumArray { 2 int[] nums; 3 HashMap<String,Integer> map; 4 public NumArray(int[] nums) { 5 this.nums = nums; 6 this.map = new HashMap(); 7 } 8 9 public int sumRange(int i, int j) { 10 if(map.containsKey(i+"-"+j)){ 11 return map.get(i+"-"+j); 12 } 13 int sum = 0; 14 for(int k=i;k<=j;k++){ 15 sum+=this.nums[k]; 16 } 17 map.put(i+"-"+j,sum); 18 return sum; 19 } 20 } 21 22 /** 23 * Your NumArray object will be instantiated and called as such: 24 * NumArray obj = new NumArray(nums); 25 * int param_1 = obj.sumRange(i,j); 26 */
我们提前维护一个前缀和数组int frontSum[]，该数组的第i个元素表示数据数组nums 从0 ~ i-1的和，这样，我们在O(n)的时间里求出了部分和数组，查询时只需求frontSum[j+1] - frontSum[i]即可，查询时间为O(1)。
1 class NumArray {//前缀和 2 int[] frontSum; 3 public NumArray(int[] nums) { 4 this.frontSum = new int[nums.length+1]; 5 for(int i = 1;i < frontSum.length;i++){ 6 frontSum[i] = frontSum[i-1] + nums[i-1]; 7 } 8 } 9 10 public int sumRange(int i, int j) { 11 return this.frontSum[j+1] - this.frontSum[i]; 12 } 13 }
既然有前缀和，那分块有啥用呢？事实上，分块是解决很多区间查询问题的通用「大杀器」。如果我们把这题修改一下，除了 sumRange(i, j) 这一查询操作之外，我们增加一个 update(i, x) 操作，将数组元素 nums[i] 的值修改为 xx，那么使用前缀和处理修改操作时，就需要使用 O(n) 的时间，将从 i开始的前缀和全部重新计算一遍。而使用分块方法的话，只需要找到位置 i 对应的块 block_size，使用 O(1)的时间修改这个块的部分和即可。
1 class NumArray { 2 int blockSize = 100; // blockSize取法：blockSize * bockSize >= nums.length 3 int[] nums; 4 int[] block; // block[i] 表示[i, i + blockSize - 1]之间的区间和； 可以定义成 ArrayList 5 6 public NumArray(int[] nums) { 7 this.nums = nums; 8 block = new int[nums.length / blockSize + 1]; 9 int idx = 0; 10 for (int i = 0; i + blockSize <= nums.length; i += blockSize) { 11 int curSum = 0; 12 for (int j = 0; j < blockSize; j++) // 当前块的元素和 13 curSum += nums[i + j]; 14 block[idx++] = curSum; 15 } 16 } 17 18 public int sumRange(int i, int j) { 19 int k = i, res = 0; 20 while (k <= j) { 21 // k 右边有个完整块 22 if (k % blockSize == 0 && k + blockSize - 1 <= j) { 23 res += block[k / blockSize]; 24 k += blockSize; 25 // k 右边不够一个块 26 } else { 27 res += nums[k]; 28 k++; 29 } 30 } 31 return res; 32 } 33 34 // 把 i 位置的元素改成 data 35 public void update(int i, int data) { 36 int blockIdx = i / blockSize; 37 block[blockIdx] -= nums[i]; 38 block[blockIdx] += data; 39 40 nums[i] = data; 41 } 42 }
原文：https://www.cnblogs.com/WhiteThornZzf/p/14462127.html