@vishveshcoder
Hi,I will try to explain on how the updation works in case of sparse table.
If you don’t know about sparse table I would recommend you to go through topcoder tutorial first. It is quite easy to understand everything related to sparse table.
Still If you are having trouble in understanding then I will explain the main idea behind sparse table-
For each index ‘i’ in the array we store the minimum of all continuous subarray of length 2^k(k belongs to whole number {0,1,2,…} ) which start at index ‘i’ till (i+2^k) is less than n(size of array).
Representation is table[i][k] where i is the index and 2^k is the length of the continuous subarray.arr[] is the array containing the elements.
For eg: if we are index i = 5 and lets say the size of array is n = 22, then for index i = 5 we will store the following information(this information is only for index i=5, we have to store such type of information for every node) :-
For k = 0, length = 2^k => length = 1, we store the minimum of subarray of length = 1 starting at index i = 5, which means minimum of index i = 5 only. So we have only one element and minimum of it will be itself only. => (table[5][0] = arr[5])
For k=1, length = 2^k -> length = 2, we store the minimum of subarray of length = 2 starting at index i = 5, which means minimum of index i = 5 and i = 6. => (table[5][1] = min(arr[5],arr[6]) )
For k=2, length = 2^k -> length = 4, we store the minimum of subarray of length = 4 starting at index i = 5, which means minimum of index i = 5,i = 6,i = 7 and i = 8.=> (table[5][2] = min(arr[5],arr[6],arr[7],arr[8]) )
For k=3, length = 2^k -> length = 8, we store the minimum of subarray of length = 8 starting at index i = 5, which means minimum of index i = 5 till i = 12 (from index 5 to 12 we have 8 elements). => (table[5][3] = min(arr[5], … ,arr[12]) )
For k=4, length = 2^k -> length = 16, we store the minimum of subarray of length = 16 starting at index i = 5, which means minimum of index i = 5 till i = 20 (from index 5 to 20 we have 16 elements). => (table[5][4] = min(arr[5], … ,arr[20]) )
For k=5, length = 2^k -> length = 32, we store the minimum of subarray of length = 32 starting at index i = 5, which means minimum of index i = 5 till i = 36 => (from index 5 to 36 we have 32 elements).
But for the last case k = 5, we can’t go till index 36 since size of array is n = 22 only, so we will store the minimum till 22 only for k = 5. => (table[5][5] = min(arr[5], … ,arr[22]) )
Now must be wondering on how to store these values, right?
Before that, Please understand that for each value of k, we will store answer for each element in the array and then we will increase our K, meaning, for k = 0 I will store the answer for each element and then only I will move on to k = 1. Similarly after I have stored the value(for k = 1) for each element, then only I will increment my k. So with that in mind, now you can move on to an example which will do 90% of the work itself.
Let’s say you are at index i = 5 and you need to calculate minimum for k = 4(length = 16, from index 5 till 20).
Also, we know the answer for k=3 for each element in the array (How? please read the above paragraph once again).
So now I will use the value stored for k = 3 to calculate the value for k = 4(which is a basic DP too).
For index i=5 and for k=4, the value will be MINIMUM of table[5][3] and table[13][3] . Because table[5][3] stores the minimum for elements from arr[5] till arr[12] and table[13][3] will store the minimum of arr[13] till arr[20] (since from index 13 to 20 we have 8 elements or length = 2^3). So for minimum of arr[5] till arr[20] we can directly use the previous values quite easily and update our value of table[5][4] in O(1) time .
In other words we divide our current target subarray (5 - 20) in two parts and use the previously computed values, since if we are calculating for length = 16 then, we must have computed for length = 8 before.
Now for this problem, as we move down the tree from root to some node, I already have the minimum stored for the nodes which come in the path from root to the current node. So for current node we repeat the same procedure as we did above and update the minimum values for each length for current node.
If you still have any doubt, then feel free to ask.