Many times while solving a problem, I get stuck to the point where I have to do the following:-
- For every number in the range [0, N],
0 <= N <= LONG_LONG_MAX, map them to a particular value. Say, for example, “map all the values smaller than or equal to 100 to 3.” Then if ar[] stores our mappings, then after the mapping operation, ar[0] = ar[1] = … = ar[100] = 3.
- Query the result of mapping. Let’s say we first perform two mapping operations, “map all the values smaller than or equal to 5 to 1.” and “map all the values smaller than or equal to 2 to 2.” and in this order. Then after the mappings, ar[0] = 2, ar[1] = 2, ar[2] = 2, ar[3] = 1, ar[4] = 1, ar[5] = 1.
Next we perform two query operations, query(ar, 1) and query(ar, 4). The answers to which are 2(ar[1] = 2) and 1(ar[4] = 1) respectively.
So what can be an efficient approach to handle these, if both queries and mapping operations are large? Are Segment Tree/Binary Indexed Tree(Fenwick Tree) good enough or there exists a better alternative?
1 Like
According to my knowledge I guess this can be done efficiently by using lazy propagation in segment tree with O(logn) time complexity for both the query… No need to build segtree just initialize array of segtree to 0. Though your query 1 always updates from starting of the array so lazy propagation in fenwick tree could also be useful… but I haven’t tried it so I am suggesting soln in seg tree…
Query type 1 :
Now proceed as we do proceed in normal segtree and check if current segment totally intersects the range of query or not. If not then assign its value both of its child…
left_Child_Value=parent_value; right_Child_Value=parent_vlues; parent_value=0;
Now again check both child if they intersects fully with given range or not…
Do this recursively till a segment intersects it…
If current segment is fully inside the range of query then assign the value you wanted to update to that node and break.
Query type 2:
It is very easy to compute this query… traverse in the direction of this node in segment tree and check each segment which contains this element… if it is non zero than it is the current value of the element (break the loop and return the first non zero value).
1 Like
moreover If your soln requires 0 as value in update query 1 Then you can take an another boolean array to point if we have to consider this value of not… (As we checked if current code is 0 or not… In the same way we will check if it is considerable or not).
Thanks 
Have not used Lazy Propagation Seg Tree for a very long time. Looks like I need to read about it again.