Segment Tree Applications
Generally, the segment tree application problem can also be solved by Binary Search. But we only cover the Segment Tree Solution here.
Count of Small Number
Analysis: Combine Segment Tree Build, Modify, Query, the problem can be solved easily. The code is long but all the contents already covered in previous sections.
Algorithm:
Build a segment tree whose each node has an additional attribute count. Initially assign all count to 0
Modify the count attributes of the tree nodes based on the input array. Resultant tree is still valid.
Query the tree with integers from queries array. Returned integer is the corresponding smaller number
Notice:
For modify() method, it will not reassign the count to new value but adding new value on it, cause there might be multiple same integer showing in the input array.
For query() method, we choose to query by a range of 0 to queries[i]-1 rather than use single index queries[i], because one integer might have count>1.
When the input array is null or empty, need to return a sequence of zero with length = queries.length, rather than return an empty array.
public class Solution {
// Define SegmentTreeNode class
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;
}
}
// Segment Tree Build
private SegmentTreeNode build(int start, int end){
if (start > end)
return null;
if (start == end){
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
return root;
}
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
int mid = (start+end)/2;
root.left = build(start, mid);
root.right = build(mid+1, end);
return root;
}
// Segment Tree Modify
private void modify(SegmentTreeNode root, int index, int value){
if (root == null)
return;
if (index < root.start || index > root.end)
return;
// Leaf node
if (root.start == index && root.end == index){
root.count += value;
return;
}
int mid = (root.start+root.end)/2;
if (index <= mid){
modify(root.left, index, value);
}
else{
modify(root.right, index, value);
}
root.count = root.left.count + root.right.count;
}
// Segment Tree Query
private int query(SegmentTreeNode root, int start, int end){
if (root == null)
return 0;
if (start > end)
return 0;
// Query range is completely outside the root's range
if (end < root.start || start > root.end)
return 0;
// Cover the range
if (start <= root.start && end >= root.end)
return root.count;
int mid = (root.start + root.end)/2;
if (end <= mid)
return query(root.left, start, end);
if (start > mid)
return query(root.right, start, end);
return query(root.left, start, mid)+query(root.right, mid+1, end);
}
public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
ArrayList<Integer> output = new ArrayList<Integer>();
// When A contains nothing, output a sequence of 0
if (A == null || A.length == 0){
for (int m=0; m<queries.length; m++){
output.add(0);
}
return output;
}
if (queries == null || queries.length == 0)
return output;
// Find the range of segment tree
int start = findMin(A);
int end = findMax(A);
SegmentTreeNode root = build(start, end);
for (int i=0; i<A.length; i++){
modify(root, A[i], 1);
}
for (int j=0; j<queries.length; j++){
output.add(query(root, 0, queries[j]-1));
}
return output;
}
// Utility function
private int findMin(int[] A){
int min = A[0];
for (int i=1; i<A.length; i++){
min = A[i]<min?A[i]:min;
}
return min;
}
// Utility function
private int findMax(int[] A){
int max = A[0];
for (int i=1; i<A.length; i++){
max = A[i]>max?A[i]:max;
}
return max;
}
}
Interval Sum II
Notice: Need helper function to support the methods.
Interval Minimum Number
Analysis:
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
public class Solution {
// Define the class
public class SegmentTreeNode {
public int start, end, min;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int min){
this.start = start;
this.end = end;
this.min = min;
this.left = this.right = null;
}
}
// Segment Tree Build
private SegmentTreeNode build(int start, int end, int init_count){
SegmentTreeNode root = new SegmentTreeNode(start, end, init_count);
if (start > end)
return null;
if (start == end)
return root;
int mid = (start+end)/2;
root.left = build(start, mid, init_count);
root.right = build(mid+1, end, init_count);
return root;
}
// Segment Tree Modify
private void modify(SegmentTreeNode root, int index, int value){
if (root == null)
return;
if (index < root.start || index > root.end)
return;
if (index == root.start && index == root.end){
root.min = value;
return;
}
int mid = (root.start+root.end)/2;
if (index <= mid){
modify(root.left, index, value);
}
else {
modify(root.right, index, value);
}
root.min = Math.min(root.left.min, root.right.min);
}
// Segment Tree Query
private int query(SegmentTreeNode root, int start, int end){
if (root == null)
return Integer.MIN_VALUE;
if (end < root.start || start > root.end)
return Integer.MIN_VALUE;
if (root.start == start && root.end == end)
return root.min;
int mid = (root.start+root.end)/2;
if (end <= mid)
return query(root.left, start, end);
if (start > mid)
return query(root.right, start, end);
return Math.min(query(root.left, start, mid), query(root.right, mid+1, end));
}
public ArrayList<Integer> intervalMinNumber(int[] A,
ArrayList<Interval> queries) {
ArrayList<Integer> output = new ArrayList<Integer>();
if (A == null || A.length == 0 || queries.size() == 0)
return output;
// Build Segment Tree
SegmentTreeNode root = build(0, A.length-1, findMax(A));
// Modify the min attributes
for (int i=0; i<A.length; i++){
modify(root, i, A[i]);
}
// Query the Segment Tree
for (int j=0; j<queries.size(); j++){
Interval temp = queries.get(j);
output.add(query(root, temp.start, temp.end));
}
return output;
}
// Utility function
private int findMax(int[] A){
int max = A[0];
for (int i=1; i<A.length; i++){
max = A[i]>max?A[i]:max;
}
return max;
}
}
Interval Sum
Analysis: Very similar to the Interval Minimum Number problem. But the additional attribute is sum.
Notice: The output type is Long. So be careful of casting.
public class Solution {
// Define Segment Tree class
private class SegmentTreeNode {
public int start, end;
public long sum;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end){
this.start = start;
this.end = end;
this.sum = 0;
this.left = this.right = null;
}
}
// Segment Tree Build
private SegmentTreeNode build(int start, int end, int[] A){
SegmentTreeNode root = new SegmentTreeNode(start, end);
if (start > end)
return null;
if (start == end){
root.sum = A[start];
return root;
}
int mid = (start+end)/2;
root.left = build(start, mid, A);
root.right = build(mid+1, end, A);
root.sum = root.left.sum + root.right.sum;
return root;
}
// Segment Tree Query
private long query(SegmentTreeNode root, int start, int end){
if (root == null || start > end || start > root.end || end < root.start)
return 0;
if (start == root.start && end == root.end)
return root.sum;
int mid = (root.start+root.end)/2;
if (end <= mid)
return query(root.left, start, end);
if (start > mid)
return query(root.right, start, end);
return query(root.left, start, mid)+query(root.right, mid+1, end);
}
public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
// write your code here
ArrayList<Long> output = new ArrayList<Long>();
if (A == null || A.length == 0){
for (int i=0; i<queries.size(); i++){
output.add((long)0);
}
return output;
}
if (queries == null || queries.size() == 0)
return output;
// Build Segment Tree
SegmentTreeNode root = build(0, A.length-1, A);
// Query Segment Tree
for (int j=0; j<queries.size(); j++){
Interval temp = queries.get(j);
output.add(query(root, temp.start, temp.end));
}
return output;
}
}