SegmentTree, O(n) build, O(logn) query


  • 1
    L
    class SegmentTreeNode {
        public int start;
        public int end;
        public int value;
        public SegmentTreeNode left, right;
        public SegmentTreeNode (int start, int end, int value) {
            this.start = start;
            this.end = end;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
    public class NumArray {
        // M1 segmenttree
        // O(n) build, O(logn) query
        private SegmentTreeNode root;
        public NumArray(int[] nums) {
            root = build(nums, 0, nums.length - 1);
        }
        public int sumRange(int i, int j) {
            return query(root, i, j);
        }
        private SegmentTreeNode build(int[] nums, int start, int end) { // O(n)
            if (start > end) {
                return null;
            }
            SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
            if (start == end) {
                root.value = nums[start];
                return root;
            }
            int mid = start + (end - start) / 2;
            root.left = build(nums, start, mid);
            root.right = build(nums, mid + 1, end);
            root.value = root.left.value + root.right.value;
            return root;
        }
        private int query(SegmentTreeNode root, int start, int end) { // O(logn) per query
            if (root.start == start && root.end == end) {
                return root.value;
            }
            int mid = root.start + (root.end - root.start) / 2;
            if (start <= mid) {
                if (end <= mid) {
                    return query(root.left, start, end);
                } else {
                    return query(root.left, start, mid) + query(root.right, mid + 1, end);
                }
            } else {
                return query(root.right, start, end);
            }
        }
    }

  • 0

    Normally I would use segment tree to query the minimum value for a given range, I think it's a little bit of overkill for this problem, your implementation is interesting though.


  • 0
    L

    ;p Just thought there would be a follow-up with changing input. We can then plus a modify() here.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.