Object Oriented C# Solution With Explanation


  • 0

    This solution implements a Segment Tree data structure. A Segment tree is useful when needing to extract information from a range of numbers in an array; especially when the data will be queried and modified often. In this case we are interested in obtaining the sum from some starting point in the array to some ending point in the array. With minimal changes we could easily find the Max value or Min value use this same logic.

    Now for the explanation of the code. Firstly this data structure is implemented as a binary tree with additional information stating the start and end point this node spans; and the sum at this node. We start by converting our input array to its segment representation. the buildTree method recursively builds the tree creating the top nodes first but setting the sums from the bottom up. Notice the leaf nodes are the elements of the input array. Building the Segment Tree cost O(n) time. To obtain the Sum we ask the following questions 1. Is the range i want to query completely in the left tree, 2. Is the range I want to query completely in the right tree, 3. is the range in both trees 4. Are we at the exact location. Finally we consider update method, this method only updates the ancestor nodes of the array element (leaf node being upated)

    public class NumArray {
        public class Node {
            public int start, end, sum = 0;
            public Node left, right;
            public Node(int i, int j){
                start = i;
                end = j;
            }
        }
        
        Node root;
        public NumArray(int[] nums) {
            root = buildTree(nums, 0, nums.Length - 1);
        }
        
        private Node buildTree(int[] arr, int i, int j){
            if(i > j) return null;
            Node n = new Node(i,j);
            if(i == j) n.sum = arr[i];
            else{
                int mid = i + (j - i)/2;
                n.left = buildTree(arr,i,mid);
                n.right = buildTree(arr,mid+1,j);
                n.sum = n.left.sum + n.right.sum;
            }return n;
        }
    
        public int SumRange(int i, int j) {
            return SumRange(root, i, j);
        }
        
        private int SumRange(Node root, int i, int j) {
            if(root.start == i && root.end == j) return root.sum;
            int mid = root.start + (root.end - root.start)/2;
            if(i >= mid + 1) return SumRange(root.right, i, j);
            else if(j <= mid) return SumRange(root.left,i,j);
            else return SumRange(root.left, i, mid) + SumRange(root.right, mid + 1, j);
        }
        
        public void Update(int i, int val) {
            Update(root, i, val);
        }
        
        private void Update(Node root, int i, int val) {
            if(root.start == root.end) root.sum = val;
            else{
                int mid = root.start + (root.end - root.start)/2;
                if(i <= mid) Update(root.left, i, val);
                else Update(root.right, i, val);
                root.sum = root.left.sum + root.right.sum;
            }
        }
    }

Log in to reply
 

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