Merge Sort Tree (and similar stuff)

Revision en2, by Abito, 2023-11-11 20:24:28

Sometimes I encounter a type of range queries that I don't know how to do using segment tree, so I use a merge sort tree instead. It can answer queries in $$$O(log^2 n ) $$$. I decided to share this because it can be useful to many in contests. First, we know that a node in a segment tree stores the answer for a range of length $$$2^x$$$ for some $$$x$$$, but we can also store in it all the elements in the range sorted in a vector (using merge sort algo) or set or whatever. Here I am going to give a few examples how we can use this to our advantage.

Problem 1: Static Count of Lesser Elements range queries.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has three integers $$$l_i , r_i , x_i$$$. The answer for this query is how many $$$a_j$$$ such that $$$l_i \le j \le r_i$$$ and $$$a_j < x$$$.

Solution
Code

Problem 2: Dynamic Lower Bound problem.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has an integer $$$t_i$$$, describing the type of query.

  • If $$$t_i = 0$$$ then you are given two other integers, $$$idx_i$$$ and $$$x_i$$$, meaning that we should make $$$a_{idx} = x_i$$$.
  • If $$$t_i = 1$$$ then you are given three integers $$$l_i, r_i, x_i$$$. You should answer with the smallest value $$$v$$$ in the range $$$[l_i,r_i]$$$ such that $$$x \le v$$$. If there is none, print -1.
Solution
Code

Final notes

There are many other things that you can do using technique. You can even solve the dynamic version of the first problem using indexed_set. However you should use this only when you're desperate because it's really slow. Yes it's $O(nlog^2n) but the constant factor is very high because it's segment tree + sets. If you have intereseting problems to add to the blog, or you notice some mistake please say inthe comments. Good luck everyone!

Tags merge sort tree, range queries, segment tree, sets

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Abito 2023-12-13 13:50:17 72
en5 English Abito 2023-11-16 23:38:49 116
en4 English Abito 2023-11-12 12:16:05 92
en3 English Abito 2023-11-11 21:04:15 2
en2 English Abito 2023-11-11 20:24:28 12 Tiny change: 's $O(log^2 n) because w' -> 's $O(log^2n)$ because w'
en1 English Abito 2023-11-11 20:22:36 7126 Initial revision (published)