In this blog I'll cover all the intuition you need for range queries, deriving segment trees, sparse tables and sqrt decomposition. This however is not a blog explaining how to implement segment trees, sparse tables and sqrt decomposition. If you want to learn any specific algorithm from those; this blog is not for you.

What are range queries

Let's say we have an array $$$a$$$ with $$$n$$$ elements. Now we want to make a function getsum(l, r), which returns the sum of elements of this array, from the index $$$l$$$ to $$$r$$$ inclusive. For example for

getsum(0, 3) should return $$$1+2+3+4 = 10$$$. This problem can be easily solved using prefix sums ( I assume you know what prefix sums are, if not, read this first ). What if however we need to implement a second function set(i, x), which should set the $$$i$$$th element to $$$x$$$?

The simplest solution would be:

getsum(l, r) := iterate from l to r summing the numbers in a
set(i, x)    := set the ith number to x

This is $$$O(1)$$$ for set and $$$O(n)$$$ for getsum.

If we use prefix sums however we could make it:

getsum(l, r) := find the sum of [l, r] using prefix sums
set(i, x)    := set the ith number to x, and recalculate the prefix array

Now this is $$$O(n)$$$ for set and $$$O(1)$$$ for getsum.

So how can we make it faster?

Splitting into subsegments

Well let's start from the simple solution, and let's add a second array $$$b$$$. Now the array $$$b$$$ will have $$$\frac{n}{2}$$$ elements, and $$$b_i = a_{2i} + a_{2i+1}$$$. So the array $$$b$$$ will contain the sums of the $$$\frac{n}{2}$$$ subsegments of $$$a$$$ which have length two. So in our starting example we would have:

Now how does it help us? When we get a set query, we will just update the value of $$$a_i$$$ and $$$b_{\lfloor \frac{i}{2} \rfloor}$$$, and for a getsum query, we will find all the subsegments in $$$b$$$ that cover our range, and then only if something is left, add it from the $$$a$$$ array.

For example:

getsum(1, 4) = b[1] (2..3) (only full subsegment in our range) + a[1] + a[4]
set(1, 4)    = b[0] += 4 - a[1] (1/2 = 0)
               a[1] = 4

The time complexity of this solution is still $$$O(1)$$$ for set and $$$O(n)$$$ for getsum. But if we look at the number of numbers we need to sum/change, in set it goes from $$$1$$$ to $$$2$$$ (we need to update two numbers instead of one), and for getsum it goes from $$$r-l+1$$$ to $$$\frac{r-l+1}{2}+2$$$ (instead of summing the whole segment, we sum the segments in $$$b$$$ and then there are at most $$$2$$$ left in $$$a$$$).

Sqrt decomposition

Now this idea allows us to make a better algorithm: Sqrt decomposition. To do it, we start by changing the definition of $$$b$$$. The choice of length equal two, is arbitrary, and we can represent the length by some variable $$$k$$$. Now $$$b$$$ will have length $$$\frac{n}{k}$$$. Let's analyze the time complexity:

Since we still only update two numbers (one in $$$a$$$ and one in $$$b$$$) we get $$$O(1)$$$ for set, but in getsum, we will now sum $$$\frac{r - l + 1}{k} + 2 \cdot (k - 1)$$$ numbers. That is because there will be $$$\frac{r - l + 1}{k}$$$ blocks from $$$b$$$ used and at the end we will need at most $$$2 \cdot (k - 1)$$$ from $$$a$$$. This simplifies to $$$O(\frac{n}{k} + k)$$$ worst case and is minimized for $$$k = \sqrt{n}$$$ (proof is left as an exercise for the reader). So getsum becomes $$$O(\sqrt{n})$$$, which is much better than $$$O(n)$$$.

Now after reading this blog, before moving onto the next part, try to implement both of those algorithms!

Next blog soon (about segment trees).