首页 > itarticle > [leetcode] problem 307 – range sum query – mutable

[leetcode] problem 307 – range sum query – mutable

admin 11月 13, 2020 0

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.

Segment Tree

public class  {
    private int start;
    private int end;
    private int sum;
    private SegmentTreeNode left;
    private SegmentTreeNode right;

    public (int start, int end, int sum) {
        this.start = start;
        this.end = end;
        this.sum = sum;
    }
}

public class SegmentTree {
    private SegmentTreeNode root;

    public SegmentTree (int[] nums, int start, int end) {
        this.root = build(nums, start, end);
    }

    private SegmentTreeNode build(int[] nums, int start, int end) {
        if (start > end)
            return null;

        SegmentTreeNode node = new SegmentTreeNode(start, end, 0);

        if (start != end) {
            int mid = (start + end) / 2;
            node.left = build(nums, start, mid);
            node.right = build(nums, mid + 1, end);
            node.sum = node.left.sum + node.right.sum;
        }
        else 
            node.sum = nums[start];
        
        return node;
    }

    public void modify(int index, int value) {
        modify(root, index, value);
    }

    private void modify(SegmentTreeNode node, int index, int value) {
        if (node.start == index && node.end == index) {
            node.sum = value;
            return;
        }

        int mid = (node.start + node.end) / 2;

        if (index <= mid)
            modify(node.left, index, value);
        else
            modify(node.right, index, value);
        
        node.sum = node.left.sum + node.right.sum;
    }

    public int query(int start, int end) {
        return query(root, start, end);
    }

    private int query(SegmentTreeNode node, int start, int end) {
        if (start == node.start && end == node.end)
            return node.sum;
        
        int mid = (node.start + node.end) / 2;

        if (end <= mid)
            return query(node.left, start, end);
        else if (start >= mid + 1)
            return query(node.right, start, end);
        else 
            return query(node.left, start, mid) + query(node.right, mid + 1, end);
    }
}

private SegmentTree tree;

public NumArray(int[] nums) {
    tree = new SegmentTree(nums, 0, nums.length - 1);
}

public void update(int i, int val) {
    tree.modify(i, val);
}

public int sumRange(int i, int j) {
    return tree.query(i, j);
}

Binary Indexed Tree

public class BinaryIndexedTree {
    private int[] sum;

    public BinaryIndexedTree(int n) {
        sum = new int[n + 1];
    }

    public void update(int i, int delta) {
        while (i < sum.length) {
            sum[i] += delta;
            i += lowbit(i);
        }
    }

    public int query(int i) {
        int result = 0;

        while (i > 0) {
            result += sum[i];
            i -= lowbit(i);
        }

        return result;
    }

    private int lowbit(int x) {
        return x & (-x);
    }
}

private BinaryIndexedTree tree;
private int[] nums;

public NumArray(int[] nums) {
    this.nums = nums;
    tree = new BinaryIndexedTree(nums.length);

    for (int i = 0; i < nums.length; i++)
        tree.update(i + 1, nums[i]);
}

public void update(int i, int val) {
    tree.update(i + 1, val - nums[i]);
    nums[i] = val;
}

public int sumRange(int i, int j) {
    return tree.query(j + 1) - tree.query(i);
}