Tuesday, December 22, 2015

Leetcode: 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:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.
Naive Solution 1: 
The first method is the most straight-forward. Use an array to store the numbers. So the update takes O(1) time. sumRange() takes O(n) time. 

Naive Solution 2:
Similar to the Range Sum Query - Immutable, we calculate the prefix of the elements in the array. Therefore, for the update(), it takes O(n) time to update the elements after the updated element. But the sumRange() take O(1) time. 

Better Solution:
Since the problem assumes that the two functions are called evenly, there exists a better method using Segment Tree in O(logn) time. 

Code (Java):
public class NumArray {
    class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left, right;
        
        // Constructor
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            sum = 0;
        }
        
        public SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
        
    }
    
    private SegmentTreeNode root;
    
    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        root = buildSegmentTree(nums, 0, nums.length - 1);
    }

    void update(int i, int val) {
        updateHelper(root, i, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int i, int val) {
        if (root == null) {
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        if (i <= mid) {
            updateHelper(root.left, i, val);
        } else {
            updateHelper(root.right, i, val);
        }
        
        if (root.start == root.end && root.start == i) {
            root.sum = val;
            return;
        }
        
        root.sum = root.left.sum + root.right.sum;

    }

    public int sumRange(int i, int j) {
        return sumRangeHelper(root, i, j);
    }
    
    private int sumRangeHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || end < root.start || start > root.end || 
            start > end) {
            return 0;
        }
        
        if (start <= root.start && end >= root.end) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        return sumRangeHelper(root.left, start, Math.min(end, mid)) + 
               sumRangeHelper(root.right, Math.max(mid + 1, start), end);
    }
    
    private SegmentTreeNode buildSegmentTree(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0 || start > end) {
            return null;
        }
        
        // Start == end
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
        }
        
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        int mid = start + (end - start) / 2;
        root.left = buildSegmentTree(nums, start, mid);
        root.right = buildSegmentTree(nums, mid + 1, end);
        
        root.sum = root.left.sum + root.right.sum;
        
        return root;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

Summary:
The take-away message for this problem is there is no such a BEST solution ever. You need to communicate with the interviewer to ask the use cases and choose the best solution. 

Update on 5/16/19:
class NumArray {
    SegmentTree segmentTree;

    public NumArray(int[] nums) {
        segmentTree = new SegmentTree(nums);
    }
    
    public void update(int i, int val) {
        segmentTree.update(i, val);
    }
    
    public int sumRange(int i, int j) {
        return segmentTree.search(i, j);
    }
}

class SegmentTree {
    public SegmentTreeNode root;
    public SegmentTree(int[] nums) {
        root = build(nums);
    }
    
    public int search(int start, int end) {
        return searchHelper(root, start, end);
    }
    
    private int searchHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || start > end) {
            return 0;
        }
        
        if (root.start == start && root.end == end) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        int leftSum = searchHelper(root.left, Math.max(root.start, start), Math.min(mid, end));
        int rightSum = searchHelper(root.right, Math.max(start, mid + 1), Math.min(root.end, end));
        
        return leftSum + rightSum;
    }
    
    public void update(int index, int val) {
        updateHelper(root, index, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int index, int val) {
        if (root == null) {
            return;
        }
        
        if (root.start == root.end && index == root.start) {
            root.sum = val;
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        if (index <= mid) {
            updateHelper(root.left, index, val);
        } else {
            updateHelper(root.right, index, val);
        }
        
        root.sum = root.left.sum + root.right.sum;
    } 
    
    private SegmentTreeNode build(int[] nums) {
        return buildHelper(0, nums.length - 1, nums);
    }
    
    private SegmentTreeNode buildHelper(int start, int end, int[] nums) {
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
        }
        
        int mid = start + (end - start) / 2;
        SegmentTreeNode leftChild = buildHelper(start, mid, nums);
        SegmentTreeNode rightChild = buildHelper(mid + 1, end, nums);
        
        SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.sum + rightChild.sum);
        root.left = leftChild;
        root.right = rightChild;
        
        return root;
    }
    
}

class SegmentTreeNode {
    int sum;
    int start, end;
    SegmentTreeNode left, right;
    
    public SegmentTreeNode(int start, int end, int sum) {
        this.sum = sum;
        this.start = start;
        this.end = end;
        left = right = null;
    }
}

/**
 * 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);
 */

Leetcode: Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Understand the problem:
Construct a 2D array sums[row+1][col+1]
(notice: we add additional blank row sums[0][col+1]={0} and blank column sums[row+1][0]={0} to remove the edge case checking), so, we can have the following definition
sums[i+1][j+1] represents the sum of area from matrix[0][0] to matrix[i][j]
To calculate sums, the ideas as below
+-----+-+-------+     +--------+-----+     +-----+---------+     +-----+--------+
|     | |       |     |        |     |     |     |         |     |     |        |
|     | |       |     |        |     |     |     |         |     |     |        |
+-----+-+       |     +--------+     |     |     |         |     +-----+        |
|     | |       |  =  |              |  +  |     |         |  -  |              |
+-----+-+       |     |              |     +-----+         |     |              |
|               |     |              |     |               |     |              |
|               |     |              |     |               |     |              |
+---------------+     +--------------+     +---------------+     +--------------+

   sums[i][j]      =    sums[i-1][j]    +     sums[i][j-1]    -   sums[i-1][j-1]   +  

                        matrix[i-1][j-1]
So, we use the same idea to find the specific area's sum.
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+
|               |   |         |    |   |   |           |   |         |    |   |   |          |
|   (r1,c1)     |   |         |    |   |   |           |   |         |    |   |   |          |
|   +------+    |   |         |    |   |   |           |   +---------+    |   +---+          |
|   |      |    | = |         |    | - |   |           | - |      (r1,c2) | + |   (r1,c1)    |
|   |      |    |   |         |    |   |   |           |   |              |   |              |
|   +------+    |   +---------+    |   +---+           |   |              |   |              |
|        (r2,c2)|   |       (r2,c2)|   |   (r2,c1)     |   |              |   |              |
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+


Code (Java):
public class NumMatrix {
    private int[][] matrix;
    private int[][] sum;
    
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        
        if (matrix == null || matrix.length == 0) {
            return;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        sum = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - 
                            sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - 
               sum[row1][col2 + 1] + sum[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);


Leetcode: Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.
Understand the problem:
For the naive solution, each time we call the sumRange(lo, hi), we sum up the numbers and return the result. So the time complexity would be O(n). 

Note that there are many calls to sumRange function, so we can calculate the prefix sum in the constructor. Then each time we call the sumRange(lo, hi), we just need to calculate the prefix[hi] - prefix[lo - 1], in O(1) time. 


Code (Java):
public class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        
        // Calculate the prefix sum
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        if (i < 0 || i >= nums.length || 
            j < 0 || j >= nums.length || 
            i > j) {
            return 0;
        }
        
        if (i == 0) {
            return nums[j];
        } else {
            return nums[j] - nums[i - 1];
        }
    }
}

Leetcode: Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Understand the problem:
A sequence DP problem. 
 -- dp[n + 1], where dp[i] means the length of the LIS, including the ith character. 
 -- Initial state: dp[0] = 0, dp[i] = 1, i >= 1
 -- Transit function: for j from [0, i), if (nums[i - 1] > nums[j - 1]), dp[i] = Math.max(dp[i], dp[j] + 1);
-- Final state: the max in dp[i]. 

Code (Java):
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.length + 1];
        for (int i = 1; i < nums.length + 1; i++) {
            dp[i] = 1;
        }
        
        int maxLen = 1;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

Follow-up: Could you solve it in O(nlogn) time?
https://leetcode.com/discuss/67609/short-java-solution-using-dp-o-n-log-n

Monday, December 21, 2015

Leetcode: Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.
For example:
Secret number:  "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 01 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".
Please note that both secret number and friend's guess may contain duplicate digits, for example:
Secret number:  "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases.
Understand the problem:
The idea is first go through the input and get the number of bulls. Meanwhile, maintain a map and update the secret number in the map. 

The second pass is to calculate the the number of cows. The method is for each character in the guess, if it is not the bull, we check if this char is in the map. If yes, we found one cow. Remember we need to remove the visited chars in the map because of the duplicated number may occur in the secret. 

Code (Java):
public class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || secret.length() == 0 || 
            guess == null || guess.length() == 0) {
            return "0A0B";
        }
        
        int numBulls = 0;
        int numCows = 0;
        
        Map<Character, Integer> map = new HashMap<>();
        
        // Step 1: calculate the number of bulls and update the map
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            
            if (s == g) {
                numBulls++;
            } else {
                // Update the map
                if (map.containsKey(s)) {
                    int freq = map.get(s);
                    freq++;
                    map.put(s, freq);
                } else {
                    map.put(s, 1);
                }
            }
        }
        
        // Step 2: calculate the number of cows
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            
            if (s != g) {
                if (map.containsKey(g)) {
                    numCows++;
                    // update the map
                    if (map.get(g) == 1) {
                        map.remove(g);
                    } else {
                        int freq = map.get(g);
                        freq--;
                        map.put(g, freq);
                    }
                }
            }
        }
        
        return numBulls + "A" + numCows + "B";
    }
}

Analysis:
Time: O(n)
Space O(n)

A better solution:
Since the digits are only from 0 to 9, we don't need a map to store the digits, but just use two arrays, and count the freq for each digit. 

Code (Java):
public class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || secret.length() == 0 || 
            guess == null || guess.length() == 0) {
                return "0A0B";
        }
        
        int numBulls = 0;
        int numCows = 0;
        int[] s = new int[10];
        int[] g = new int[10];
        
        // Step 1: count the number of bulls
        for (int i = 0; i < secret.length(); i++) {
            char charS = secret.charAt(i);
            char charG = guess.charAt(i);
            
            if (charS == charG) {
                numBulls++;
            } else {
                s[charS - '0']++;
                g[charG - '0']++;
            }
        }
        
        // Step 2: count the number of cows
        for (int i = 0; i < 10; i++) {
            numCows += Math.min(s[i], g[i]);
        }
        
        return numBulls + "A" + numCows + "B";
    }
}

Sunday, December 20, 2015

Leetcode: Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
   1
    \
     3
    / \
   2   4
        \
         5
Longest consecutive sequence path is 3-4-5, so return 3.
   2
    \
     3
    / 
   2    
  / 
 1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

Solution using global variables:
Maintain two variables, one is the local length of the consecutive path, the other is the global variable of the longest local length. 

We do a DFS, i.e, pre-order traversal of a binary tree. For each node of which value equals to the target value (parent value plus one), increase the local length. Otherwise, set the local length to 1. Meanwhile, update the global length. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxLen = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        longestConsecutiveHelper(root, 1, root.val + 1);
        return maxLen;
    }
    
    private void longestConsecutiveHelper(TreeNode root, int length, int target) {
        if (root == null) {
            return;
        }
        
        int curLen = 0;
        if (root.val == target) {
            curLen = length + 1;
        } else {
            curLen = 1;
        }
        
        maxLen = Math.max(maxLen, curLen);
        longestConsecutiveHelper(root.left, curLen, root.val + 1);
        longestConsecutiveHelper(root.right, curLen, root.val + 1);
        
    }
}

Solution without using global variables:
We can use the return value to pass the global maximal length. Then everything else is the same as the previous solution. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return longestConsecutiveHelper(root, 0, root.val + 1);
    }
    
    private int longestConsecutiveHelper(TreeNode root, int curLen, int target) {
        if (root == null) {
            return curLen;
        }
        
        if (root.val == target) {
            curLen += 1;
        } else {
            curLen = 1;
        }
        
        int left = longestConsecutiveHelper(root.left, curLen, root.val + 1);
        int right = longestConsecutiveHelper(root.right, curLen, root.val + 1);
        
        return Math.max(curLen, Math.max(left, right));
    }
}

Saturday, December 19, 2015

Leetcode: Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: 
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.
For example:
add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Understand the problem:
Use two heaps. The maxHeap stores the number which is less than the current number. The minHeap stores the number which is greter than the current number. 
We also need to keep the two heaps balanced in size. 

For the method findMedian(), we need to check if the two heaps have the same size. If yes, there must be even number of elements so far, so the median is the average of the top of the minHeap and the maxHeap. If not, i.e. odd number of elements so far, the median is the top of the heap which one more element. 

Code (Java):
import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> leftPQ = 
        new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> rightPQ = new PriorityQueue<>();
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        if (leftPQ.isEmpty() || num <= leftPQ.peek()) {
            leftPQ.offer(num);
        } else {
            rightPQ.offer(num);
        }
        
        // Rebalance the pqs
        if (leftPQ.size() - rightPQ.size() > 1) {
            rightPQ.offer(leftPQ.poll());
        } else if (rightPQ.size() - leftPQ.size() > 1) {
            leftPQ.offer(rightPQ.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (leftPQ.isEmpty() && rightPQ.isEmpty()) {
            throw new NoSuchElementException(); // if the queue is empty
        }
        
        if(leftPQ.isEmpty()) {
            return (double) rightPQ.peek();
        } else if (rightPQ.isEmpty()) {
            return (double) leftPQ.peek();
        } else if (leftPQ.size() > rightPQ.size()) {
            return (double) leftPQ.peek();
        } else if (rightPQ.size() > leftPQ.size()) {
            return (double) rightPQ.peek();
        } else {
            return (double) (leftPQ.peek() + rightPQ.peek()) / 2;
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();


Update 3/19/19:
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();

        int[] ans = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (maxPQ.isEmpty() || num <= maxPQ.peek()) {
                maxPQ.offer(num);
            } else {
                minPQ.offer(num);
            }

            rebalacne(maxPQ, minPQ);

            ans[i] = maxPQ.peek();
        }
        
        return ans;
    }

    private void rebalacne(PriorityQueue<Integer> maxPQ, PriorityQueue<Integer> minPQ) {        
        if (maxPQ.size() - minPQ.size() > 1) {
            minPQ.offer(maxPQ.poll());
        } else if (minPQ.size() - maxPQ.size() > 0) {
            maxPQ.offer(minPQ.poll());
        }
    }
}



Monday, November 30, 2015

LintCode: Segment Tree Query II

For an array, we can build a SegmentTree for it, each node stores an extra attribute count to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)
Design a query method with three parameters rootstart and end, find the number of elements in the in array's interval [startend] by the given root of value SegmentTree.
Example
For array [0, 2, 3], the corresponding value Segment Tree is:
                     [0, 3, count=3]
                     /             \
          [0,1,count=1]             [2,3,count=2]
          /         \               /            \
   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
query(1, 1), return 0
query(1, 2), return 1
query(2, 3), return 2
query(0, 2), return 2

Code(Java):
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, count;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int count) {
 *         this.start = start;
 *         this.end = end;
 *         this.count = count;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param root, start, end: The root of segment tree and 
     *                         an segment / interval
     *@return: The count number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end) {
            return 0;
        }
        
        if (end < root.start || start > root.end) {
            return 0;
        }
        
        if (start <= root.start && end >= root.end) {
            return root.count;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        return query(root.left, start, Math.min(mid, end)) + 
               query(root.right, Math.max(mid + 1, start), end);
    }
}

Update on 5/6/19:
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, count;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int count) {
 *         this.start = start;
 *         this.end = end;
 *         this.count = count;
 *         this.left = this.right = null;
 *     }
 * }
 */



public class Solution {
    /*
     * @param root: The root of segment tree.
     * @param start: start value.
     * @param end: end value.
     * @return: The count number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end) {
            return 0;
        }

        if (end < root.start || start > root.end) {
            return 0;
        }

        if (start == root.start && end == root.end) {
            return root.count;
        }

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

        int leftCount = query(root.left, Math.max(start, root.start), Math.min(mid, end));
        int rightCount = query(root.right, Math.max(mid + 1, start), Math.min(end, root.end));

        return leftCount + rightCount;
    }
}

LintCode: Segment Tree Query

For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).
Design a query method with three parameters rootstart and end, find the maximum number in the interval [start, end] by the given root of segment tree.
Example
For array [1, 4, 2, 3], the corresponding Segment Tree is:
                  [0, 3, max=4]
                 /             \
          [0,1,max=4]        [2,3,max=3]
          /         \        /         \
   [0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
query(root, 1, 1), return 4
query(root, 1, 2), return 4
query(root, 2, 3), return 3
query(root, 0, 2), return 4
Note
It is much easier to understand this problem if you finished Segment Tree Build first.

Code (Java):
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param root, start, end: The root of segment tree and 
     *                         an segment / interval
     *@return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end) {
            return Integer.MIN_VALUE;
        }
        
        if (end < root.start || start > root.end) {
            return Integer.MIN_VALUE;
        }
        
        if (start == root.start && end == root.end) {
            return root.max;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        return Math.max(query(root.left, start, Math.min(mid, end)), 
                        query(root.right, Math.max(mid + 1, start), end));
    }
}

Update on 5/6/19:
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of segment tree.
     * @param start: start value.
     * @param end: end value.
     * @return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end) {
            return Integer.MIN_VALUE;
        }

        if (end < root.start || start > root.end) {
            return Integer.MIN_VALUE;
        }

        if (start == root.start && end == root.end) {
            return root.max;
        }

        int mid = root.start + (root.end - root.start) / 2;
        if (end <= mid) {
            return query(root.left, start, end);
        } else if (start >= mid + 1) {
            return query(root.right, start, end);
        } else {
            int leftMax = query(root.left, start, mid);
            int rightMax = query(root.right, mid + 1, end);
            return Math.max(leftMax, rightMax);
        }
    }
}

LintCode: Segment Tree Build II

The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
  • The root's start and end is given by build method.
  • The left child of node A has start=A.left, end=(A.left + A.right) / 2.
  • The right child of node A has start=(A.left + A.right) / 2 + 1, end=A.right.
  • if start equals to end, there will be no children for this node.
Implement a build method with a given array, so that we can create a corresponding segment tree with every node value represent the corresponding interval max value in the array, return the root of this segment tree.
Example
Given [3,2,1,4]. The segment tree will be:
                 [0,  3] (max = 4)
                  /            \
        [0,  1] (max = 3)     [2, 3]  (max = 4)
        /        \               /             \
[0, 0](max = 3)  [1, 1](max = 2)[2, 2](max = 1) [3, 3] (max = 4)
Clarification
Segment Tree (a.k.a Interval Tree) is an advanced data structure which can support queries like:
  • which of these intervals contain a given point
  • which of these points are in a given interval

Code (Java):
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param A: a list of integer
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return null;
        }
        
        return buildHelper(A, 0, A.length - 1);
    }
    
    private SegmentTreeNode buildHelper(int[] A, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        
        if (lo == hi) {
            SegmentTreeNode node = new SegmentTreeNode(lo, hi, A[lo]);
            return node;
        }
        
        int mid = lo + (hi - lo) / 2;
        SegmentTreeNode root = new SegmentTreeNode(lo, hi);
        
        root.left = buildHelper(A, lo, mid);
        root.right = buildHelper(A, mid + 1, hi);
        
        root.max = Math.max(root.left.max, root.right.max);
        
        return root;
    }
}

LintCode: Segment Tree Build

The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
  • The root's start and end is given by build method.
  • The left child of node A has start=A.left, end=(A.left + A.right) / 2.
  • The right child of node A has start=(A.left + A.right) / 2 + 1, end=A.right.
  • if start equals to end, there will be no children for this node.
Implement a build method with two parameters start and end, so that we can create a corresponding segment tree with every node has the correct start and end value, return the root of this segment tree.
Example
Given start=0, end=3. The segment tree will be:
               [0,  3]
             /        \
      [0,  1]           [2, 3]
      /     \           /     \
   [0, 0]  [1, 1]     [2, 2]  [3, 3]
Given start=1, end=6. The segment tree will be:
               [1,  6]
             /        \
      [1,  3]           [4,  6]
      /     \           /     \
   [1, 2]  [3,3]     [4, 5]   [6,6]
   /    \           /     \
[1,1]   [2,2]     [4,4]   [5,5]
Clarification
Segment Tree (a.k.a Interval Tree) is an advanced data structure which can support queries like:
  • which of these intervals contain a given point
  • which of these points are in a given interval

Code (Java):
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param start, end: Denote an segment / interval
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int start, int end) {
        // write your code here
        if (start > end) {
            return null;
        }
        
        if (start == end) {
            SegmentTreeNode node = new SegmentTreeNode(start, end);
            return node;
        }
        
        int mid = start + (end - start) / 2;
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        root.left = build(start, mid);
        root.right = build(mid + 1, end);
        
        return root;
    }
}