Range-Query

Given an array where we have to perform two types of operations.
1->find kth smallest between (l,r);
2->update ith element to j;
(0<=l<=r<n)

Please post the original link of that question

Assuming that you know C++ to a good degree, I suggest you to look at editorial of this problem.

you can use a advanced data structures like segment tree or binary indexed tree or if it is an offline algorithm(https://www.quora.com/What-is-offline-programming-in-reference-of-competitive-programming)
then you can use Mo’s algorithm as well … there are other data structures but with some constraints like update is not possible(immutable data can only be stored) like sparse table and lowest common ancestor.

I would always suggest segment tree because it is like a superset of all the aforesaid range query data structures and also it requires O(log n) time per query and per update operation and requires O(n) time for construction of segment tree. The space complexity is O(n).So , from all aspects it is highly recommended for any range query related problems.

You can find a nicely explained segment tree tutorial here : https://www.youtube.com/watch?v=ZBHKZF5w4YU

Happy coding :slight_smile:

Can be solved using Segment tree

You could use segment tree for solving this question .With segment tree >time will be O(Logn) for a minimum query it will take O(n) for processing. When you are using segment tree implement as follows Leaf Nodes as elements of array And each internal node should represent the minimum of all leaves under it.


//