307. Range Sum Query - Mutable

Tags: ‘Binary Indexed Tree’, ‘Segment Tree’

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.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Solution

线段树 Segment Tree https://www.jianshu.com/p/91f2c503e62f

有时遇到这种问题：给你一个int[] nums，需要两种操作：

update nums[i]
查询某个区间内的最大值（minimum, maximum, sum, greatest common divisor, least common denominator）

一个朴素算法是：对于update，直接nums[i] = x, 时间复杂度O(1). 对于aggreation，直接遍历[start, end], 复杂度O(n)

缺点：query的最大复杂度O(N)，如果有Q个query，O(QN)

方法1： TreeNode 实现 Segment Tree, Update 和 Query 都是O(logN) 33% 62%

class NumArray {
    private class SegmentTreeNode {
        private int start, end, sum;
        private SegmentTreeNode left, right;
        private SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
            this.left = null;
            this.right = null;
        }
    }
    
    private SegmentTreeNode root;
    public NumArray(int[] nums) {
        this.root = buildHelper(0, nums.length - 1, nums);
    }
    // recursive build
    private SegmentTreeNode buildHelper(int left, int right, int[] A) {
        if (left > right) return null;

        SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]); // initialize root fields
        if (left == right) return root;
        
        int mid = left + (right - left) / 2;
        root.left = buildHelper(left, mid, A);
        root.right = buildHelper(mid + 1, right, A);
        root.sum = root.left.sum + root.right.sum;
        /*
        如果求区间最大值： root.max = Math.max(root.left.max, root.right.max)
        */
        return root;
    }
    
    public void update(int i, int val) {
        updateHelper(root, i, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int index, int value) {
        if (root.start == root.end && root.start == index) {
            root.sum = value;
            return;
        }
        int mid = (root.start + root.end) / 2; // 判断左区间还是右区间更新
        if (index <= mid) { // 左区间更新
            updateHelper(root.left, index, value);
            root.sum = root.right.sum + root.left.sum;
        } else { // 右区间更新
            updateHelper(root.right, index, value);
            root.sum = root.left.sum + root.right.sum;
        }
        return;
    }
    
    public int sumRange(int i, int j) {
        return sumRangeHelper(this.root, i, j);
    }
    
    private int sumRangeHelper(SegmentTreeNode root, int i, int j) {
        if (i <= root.start && root.end <= j) {
            return root.sum;
        }
        int mid = (root.start + root.end) / 2;
        int ans = 0;
        if (mid >= i) {
            ans = ans + sumRangeHelper(root.left, i, j);
        }
        if (mid + 1 <= j) {
            ans = ans + sumRangeHelper(root.right, i, j);
        }
        return ans;
    }
}

方法2： Array实现Segment Tree。 71% 100%

Index i children are 2i and 2i + 1

class NumArray {
    private int[] tree;
    private int n;
    public NumArray(int[] nums) {
        n = nums.length;
        if (n > 0) {
            tree = new int[n * 2];
            
            // populate index n ~ 2n-1 with nums
            for (int i = n, j = 0; i < 2*n; i++, j++) {
                tree[i] = nums[j];
            }
            for (int i = n-1; i > 0; i--) { // populate the rest of tree[]
                tree[i] = tree[i*2] + tree[i*2 + 1];
            }
        }
    }
    
    public void update(int i, int val) {
        i = i + n; // actual position = index + n
        tree[i] = val;
        while (i > 0) { // index 0 is always empty
            int left = i;
            int right = i;
            if (i % 2 == 0) { //even, means left node
                right = i + 1;
            } else { // odd, means right node, update left
                left = i - 1;
            }
            tree[i/2] = tree[left] + tree[right];
            i = i / 2;
        }
    }
    
    public int sumRange(int i, int j) {
        i += n;
        j += n;
        int sum = 0;
        while (i <= j) {
            if ((i%2) == 1) {
                sum += tree[i];
                i++;
            }
            if ((j%2) == 0) {
                sum += tree[j];
                j--;
            }
            i = i/2;
            j = j/2;
        }
        return sum;
    }
}

方法3：可以用

Alex Blog

307. Range Sum Query - Mutable