307. Range Sum Query - Mutable

发表于 | 分类于

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:

1
2
3
4
5
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.

解法1： Segment Tree

Segment Tree的直接应用。
Segment Tree 的node需要记录range的start，end以及对应的sum。
tree需要有一个node作为root。tree提供如下几个基本的method：

1
build，update，sumRange

每一个函数基本都是通过recursion实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class NumArray {
    class SegmentTreeNode {
        int start;
        int end;
        int val;
        SegmentTreeNode left;
        SegmentTreeNode right;
        public SegmentTreeNode(int start, int end, int val) {
            this.start = start;
            this.end = end;
            this.val = val;
            left = null;
            right = null;
        }
    };
    class SegmentTree {
        SegmentTreeNode root;
        public SegmentTree(int[] nums) {
            root = build(nums, 0, nums.length - 1);
        }
        public SegmentTreeNode build(int[] nums, int start, int end) {
            if (start > end) return null;
            if (start == end) {
                return new SegmentTreeNode(start, end, nums[start]);
            }
            int mid = start + (end - start) / 2;
            SegmentTreeNode left = build(nums, start, mid);
            SegmentTreeNode right = build(nums, mid + 1, end);
            int val  = (left == null ? 0 : left.val ) + (right == null ? 0 : right.val);
            SegmentTreeNode root = new SegmentTreeNode(start, end, val);
            root.left = left;
            root.right = right;
            return root;
        }
        public void update(int i, int val) {
            update(root, i, val);
        }
        public void update(SegmentTreeNode current, int i, int val) {
            if (current.start == i && current.end == i) {
                current.val = val;
                return;
            }
            int mid = current.start + (current.end - current.start) / 2;
            if (i <= mid) {
                update(current.left, i, val);
            } else {
                update(current.right, i, val);
            }
            current.val = current.left.val + current.right.val;
            return;
        }
        public int sumRange(int i, int j) {
            return sumRange(root, i, j);
        }
        public int sumRange(SegmentTreeNode current, int i, int j) {
            if (current.start >= i && current.end <= j) return current.val;
            int mid = current.start + (current.end - current.start) / 2;
            if (j <= mid) {
                return sumRange(current.left, i, j);
            } else if (i > mid) {
                return sumRange(current.right, i, j);
            } else {
                return sumRange(current.left, i, mid) + sumRange(current.right, mid + 1, j);
            }
        }
    }
    SegmentTree tree;
    public NumArray(int[] nums) {
        tree = new SegmentTree(nums);
    }
    public void update(int i, int val) {
        tree.update(i, val);
    }
    public int sumRange(int i, int j) {
        return tree.sumRange(i, j);
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */