rickgrimes07's blog

Segment Tree Problem
By rickgrimes07, history, 13 months ago, In English

Given an array of positive integers , you have to perform Q queries . Each query can be of two types , 1 L X 0 , set arr[L]=X;

and other type be 2 L R X , find index p such that arr[p]<=X and if there is no such p , print -1.

arr size and Q are of order 1e5

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Store the index of the smallest element in the range of each node in the segment tree (take any if there are several). Queries of type 1 can be handled in $$$O(log(n))$$$ time. Queries of type 2 can be processed as follows: get indices $$$I_{1}, I_{2}, ..., I_{q}$$$ (where $$$q \le log (n)$$$), and find index with the smallest value. If it is larger than $$$X$$$, then print $$$-1$$$, otherwise print the index with the minimum value.

→ Reply
»
13 months ago, hide # |
← Rev. 2  
Vote: I like it +9 Vote: I do not like it

We can use a minimum Segment Tree for this problem.

For type 1 queries, we can do Point Update in Segment Tree, which leads to a complexity of O(log N)

For type 2 queries, we can do Binary Search on Segment Tree, which also leads to a complexity of O(log N). More details regarding to this technique : https://mirror.codeforces.com/blog/entry/83883?#comment-712331

Total complexity : O(N) for building the segment tree, and O(log N) for each query.

→ Reply