307 Range Sum Query - Mutable

Posted on | Edited on | Views:

https://leetcode.com/problems/range-sum-query-mutable/
https://www.youtube.com/watch?v=rYBtViWXYeI&feature=emb_rel_pause

Naive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums=nums;
    }
    
    public void update(int i, int val) {
        nums[i]=val;
    }
    
    public int sumRange(int i, int j) {
        int sum=0;
        for(int k=i;k<=j;k++){
            sum+=nums[k];
        }
        return sum;
    }
}

Segment Tree

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
class SegmentTreeNode {
    int start;
    int end;
    int sum;
    SegmentTreeNode left;
    SegmentTreeNode right;

    public SegmentTreeNode(){}
    public SegmentTreeNode(int start, int end, int val, SegmentTreeNode s1, SegmentTreeNode s2) {
        this.start = start;
        this.end = end;
        this.sum = val;
        this.left = s1;
        this.right = s2;
    }

    public SegmentTreeNode buildTree(int start, int end, int[] nums) {
        if (start == end) return new SegmentTreeNode(start, end, nums[start],null,null);
        int mid = (start + end) / 2;
        SegmentTreeNode left = buildTree(start, mid, nums);
        SegmentTreeNode right = buildTree(mid + 1, end, nums);
        return new SegmentTreeNode(start, end, left.sum + right.sum, left, right);
    }
    public void updateUtil(SegmentTreeNode node, int index, int val) {
        if (node.start == node.end && node.start == index) node.sum = val;
        else {
            int mid = (node.start + node.end) / 2;
            if (index <= mid) updateUtil(node.left, index, val);
            else updateUtil(node.right, index, val);
            node.sum = node.left.sum + node.right.sum;
        }
    }
    public int sumRangeUtil(SegmentTreeNode node, int i, int j) {
        if (node.start == i && node.end == j) return node.sum;
        else {
            int mid = (node.start + node.end) / 2;
            if (j <= mid) return sumRangeUtil(node.left, i, j);
            else if (i > mid) return sumRangeUtil(node.right, i, j);
            else return sumRangeUtil(node.left, i, mid) + sumRangeUtil(node.right, mid + 1, j);
        }
    }
}

class NumArray {
    SegmentTreeNode mysgt = new SegmentTreeNode();

    public NumArray(int[] nums) {
        if(nums.length==0) return;
        mysgt = mysgt.buildTree(0, nums.length-1, nums);
    }

    public void update(int i, int val) {
        if(mysgt==null) return;
        mysgt.updateUtil(mysgt, i, val);
    }

    public int sumRange(int i, int j) {
        if(mysgt==null) return 0;
        return mysgt.sumRangeUtil(mysgt, i, j);
    }
}

Build

Update

Range Sum Query

0%