Merge Sort Tree (and similar stuff)

Revision en5, by Abito, 2023-11-16 23:38:49

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 in the comments. Good luck everyone!

Problems

SPOJ — KQUERY

CF EDU Segment Tree Step 3 C

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)