cksharma.skt
BAN USERIf you are updating a value (updating at particular index) in given array). this adjustment can be done in O(log(n)) in the segement tree .. Same is the case for deletion of single element.
public void updateSegementTree(int n, int start, int end, int index, int val) {
if (start > end || start > index || end < index ) return;
if (start==end) //at leaf node
{
tree[n] = val;
return;
}
updateSegementTree( n*2 , start , (start + end ) / 2 , index, val );
updateSegementTree( n*2 + 1 , (start + end) / 2 + 1 , end , index, val );
tree[n] = max( tree[n*2] , tree[n*2 + 1] );
}
Ya CLRS , Introduction to Algorithm covers these stuffs. And geeksforgeeks.org also has some materials about this.
- cksharma.skt September 20, 2012Here by I am writing the code for implementing the segment from the series of number...
Suppose I have int[] arr = {1, 2, 3,4, 5, 6, 7, 8};
I will take one more array of size int[] tree = new int[3 * arr.length];
And I have to keep track of maximum\ value from each node forming the segment trees,
public void buildSegementTree(int n, int startRange, int endRange) {
if (startRange > endRange) return;
if (startRange == endRange) {
tree[n] = arr[startRange]; // n the index in tree keeps track of the maximum value. (when range is 1 .. ::)
buildSegementTree(n, startRange, (startRange + endRange) >> 1);
buildSegementTree(n, (startRange + endRange) / 2 + 1,
endRange);
tree[n] = Math.max(tree[2 * n], tree[2 * n + 1]);
}
}
This way each node is keeping track of the maximum value in the down tree... Similary do for minimum value. And querying which will happen in log(n).
- cksharma.skt September 20, 2012You have to use Segement Trees for this.
If you clearly read the problem, the interviewer wants to get the minimum and maximum element being tracked from a particular node.
This is what segment tree does.
It's catalan numbers.
(2 * n ) ! / ( (n + 1) ! * (n) ! ) : Catalan number can be computed using Dynamic programming as it can overflow if you simply use factorial calculation. So here by I am posting one DP silution for it.
- cksharma.skt September 20, 2012