数组求和问题

这些题有点像实现一个数组的函数操作，比如给一个数组，实现一个函数可以求解数组任意长度上的和，要求时间复杂度为O(1)，然后如果是更新数组的话，再求和该如何实现呢？

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
1
2
3
4
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
1
2
3
4
5
Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

[leetcode 303] Range Sum Query - Immutable

这个就非常简单了，属于easy的题目，对i遍历，将i前面的数全部加上即可。

public class RangeSumQueryImmutable {
    int [] nums;
    public RangeSumQueryImmutable(int[] nums) {
        for(int i=1;i<nums.length;i++)nums[i]+=nums[i-1];
        this.nums=nums;
    }
    public int sumRange(int i, int j) {
        if(i==0)return nums[j];
        else return nums[j]-nums[i-1];
    }
}

[leetcode 304] Range Sum Query 2D - Immutable

同上道题的原理，也非常简单，对每一行求和。

public class RangeSumQuery2DImmutable {
    int [][] matrix;
    public RangeSumQuery2DImmutable(int[][] matrix) {
        for(int i=0;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                matrix[i][j]+=matrix[i][j-1];
            }
        }
        this.matrix=matrix;
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res=0;
        if(col1==0){for(int i=row1;i<=row2;i++)res+=matrix[i][col2];}
        else for(int i=row1;i<=row2;i++)res+=matrix[i][col2]-matrix[i][col1-1];
        return res;
    }
}

[leetcode 307] Range Sum Query - Mutable

其实我主要是想说这道题，我继续上面的方法，哗哗哗的写了下面这个代码：

public class RangeSumQueryMutable {
    int[] nums2, nums;
    public RangeSumQueryMutable(int[] nums) {
        nums2 = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) nums2[i] = nums[i];
            else nums2[i] = nums[i] + nums2[i - 1];
        }
        this.nums = nums;
    }
    public void update(int i, int val) {
        int temp = val - nums[i];
        nums[i] = val;
        for (int j = i; j < nums.length; j++) nums2[j] += temp;
    }
    public int sumRange(int i, int j) {
        if (i == 0) return nums2[j];
        else return nums2[j] - nums2[i - 1];
    }
}

我看着update确实有点复杂呢，leetcode上submit后超时了，最后一个test没有过，然后看了看discuss上第一的解法，一个感叹啊，总是让人惊奇，使用的是分割树，至少是将update函数时间复杂度从O(n)降到了O(lgn)，但是sunRange函数却是O(lgn)，也就是2O(lgn)和O(n)的区别，我只是觉得方法很好，佩服佩服，我就不会利用这些学过的知识，或许太急功近利了吧…

class NumArray {
    class SegmentTreeNode {
        int start, end;
        SegmentTreeNode left, right;
        int sum;
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            this.left = null;
            this.right = null;
            this.sum = 0;
        }
    }
    SegmentTreeNode root = null;
    public NumArray(int[] nums) {
        root = buildTree(nums, 0, nums.length - 1);
    }
    private SegmentTreeNode buildTree(int[] nums, int s, int e) {
        if (s > e) return null;
        SegmentTreeNode ret = new SegmentTreeNode(s, e);
        if (s == e) {
            ret.sum = nums[s];
            return ret;
        }
        int mid = s + (e - s) / 2;
        ret.left = buildTree(nums, s, mid);
        ret.right = buildTree(nums, mid + 1, e);
        ret.sum = ret.left.sum + ret.right.sum;
        return ret;
    }
    void update(int i, int val) {
        update(root, i, val);
    }
    private void update(SegmentTreeNode root, int pos, int val) {
        if (root.start == root.end) {
            root.sum = val;
            return;
        }
        int mid = root.start + (root.end - root.start) / 2;
        if (mid < pos) update(root.right, pos, val);
        else update(root.left, pos, val);
        root.sum = root.left.sum + root.right.sum;
    }
    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
    private int sumRange(SegmentTreeNode root, int i, int j) {
        if (root.start == i && root.end == j) return root.sum;
        int mid = root.start + (root.end - root.start) / 2;
        if (mid < i) return sumRange(root.right, i, j);
        else if (mid >= j) return sumRange(root.left, i, j);
        else return sumRange(root.left, i, mid) + sumRange(root.right, mid + 1, j);
    }
}