IntroductionHi! Since I couldn't find a tutorial on this data structure and I decided to make one myself. I don't know if this data structure has a name so I am just using the name I saw it being referred to on codeforces i.e. Disjoint Sparse Table or DST. So before diving into its structure and working let's talk what it supports and when can it be used Suppose you are given an array $A$ of size $N$ and you are asked to perform $Q$ queries. Now with a sparse table, you can answer these queries in $\mathcal{O}(\ln N)$ with $\Theta(N \ln N)$ preprocessing. Let $N' = 2^{\lceil \ln N \rceil}$. Then with disjoint sparse table we can answer the queries in $\Theta (1)$ with $\Theta(N' \ln N')$ preprocessing. Note:
As you can see you won't need to use this DS in most problems. As problems with immutable data and with tight time constraints are very rare. StructureIts structure is same as a segment tree. Each node stores information related to a range of indexes $[L, R)$.
Pardon my subpar MS paint skills.
Note: It should be depth not height in the image
Now consider a node corresponding to $[L, R)$ and the middle index $M = \frac{L+R}{2}$. BuildingNow to build a node corresponding to $[L, R)$. We first compute all the required precomputed values in $\Theta(RL)$ and recursively build its child nodes. Let the time complexity to build a tree with root of size $X$ be $T(X)$ then $$T(X) = 2 T(^X/_2) + \Theta(X)$$ $$\Rightarrow T(X) = \Theta(X \ln X)$$ So Time complexity to build a DST is equal to $\Theta(N \ln N)$. QueryingWe can answer Queries recursively similar to how we do in segment tree. Let us say we are in node $[L, R)$ and we need to answer query corresponding to $[X, Y]$; then if $X \le M \le Y$ then we an answer in $\Theta(1)$ provided we can merge answers of $[X, M]$ and $[M+1, Y]$ in $\Theta(1)$. else the range $[X, Y]$ is completely in one of the child node ranges and we move the query downwards to that node. So Time Complexity for querying would be $\mathcal{O}(\ln N)$. Note that worst case happen in cases like $X=Y= \frac {N}{2}  1$. Improving Time ComplexityLet's increase the size of array $A$ to $N' = 2^{\lceil \ln N \rceil}$ i.e. till its size becomes a power of 2. Note that this wouldn't change the answer to any query.Let $x =\lceil \ln N \rceil$. Now consider the $j^{th}$ node (0based indexing from left) at depth $i$. It's $size = \frac{N'}{2^i}$. It would correspond to $\left[ \frac{N'}{2^i}\times j, \frac{N'}{2^i}\times (j+1)\right)$. Its $M = j \times \frac{N'}{2^{i}} + \frac{N'}{2^{i+1}}$. Consider M's binary representation. It would be of the form Now lets say we are asked to answer a query $[L, R]$. Removing $L=R$ trivial case we can say that $L < R$ and binary representation of L and R would be of the form: $ \begin{matrix} L& = b_0b_1b_3 \ldots b_{k_1}& 0 & l_1 & l_2 & \ldots & l_{k_2} \\ R& = b_0b_1b_3 \ldots b_{k_1}& 1 & r_1 & r_2 & \ldots & r_{k_2} \\ \hline M& = b_0b_1b_3 \ldots b_{k_1}& 1 & 0 & 0 & \ldots & 0 \end{matrix} $ Note that $k_2 = \text{word size }  \text{number of leading zeroes of }L \oplus R  1$. One can see that binary representation of $X$ and $Y$ would be as follows $ \begin{matrix} M& = b_0b_1b_3 \ldots b_{k_1}& 1 & 0 & 0 & \ldots & 0 \\ X& = b_0b_1b_3 \ldots b_{k_1}& 0 & 0 & 0 & \ldots & 0 \\ Y& = b_0b_1b_3 \ldots b_{k_1}& 1 & 1 & 1 & \ldots & 1 \end{matrix} $ Thus $X \le L < R \le Y$. Considering that the microprocessor has BSR(Bit Scan Reverse) operation we can determine the node, that can answer the query in $\Theta(1)$, in $\Theta(1)$. So now each query can be answered in $\Theta(1)$. ImplementationWe can see that each level sum of sizes of nodes is equal to $N$. So We can simply use a 2 dimensional array to store DST. I will explain with an example: Solution to range product query:Suppose we are given an array an array $A$ and a number $P$ and we are asked to answer $Q$ queries: Global variables and constants:
Then some initialisations:
Then the build function(the preprocessing part):
We call build() to initialize the DST. Now to answer query [X, Y] we use
Note:
You can try solving SEGPROG with this DS. Credits
asked 18 Nov '17, 03:12
showing 5 of 6
show all

Nice tutorial! The explanation of how it works was clear :) int n = 1; while(n < N) n <<= 1; int range, half; for(int h = 1; (range = 1 << h) <= n; h++) { half = range >> 1; for(int i = half; i < n; i += range) { t[h][i  1] = A[i  1]; for(int j = i  2; j >= i  half; j) t[h][j] = t[h][j + 1] * A[j] % P; t[h][i] = A[i]; for(int j = i + 1; j < i + half; j++) t[h][j] = t[h][j  1] * A[j] % P; } } Note that if(L == R) result = A[L]; else { int h = number_of_bits_in_int  __builtin_clz(L ^ R); result = t[h][L] * t[h][R] % P; } Additionaly, if a BSR operation is not available there are some alternate ways get calculate the position of highest set bit fast using bitwise operations. You can find a few such ways here. answered 19 Nov '17, 16:06
Your implementation is much cleaner! Storing prefixes till $M1$ helps us avoid ifcondition in query. In using height instead of depth we no longer need to store $x$. Also here $h = \lfloor \ln {(L \oplus R)} \rfloor + 1$. Which can also be computed in $O(\ln(\ln N))$ ~5 operations with precomputation/look up table.
(19 Nov '17, 19:10)
@meooow, there is a inbuilt function to compute highest bit in O(1). It is __lg(i). Basically it returns $\lfloor{log_2 n}\rfloor$, which would also be the highest bit in number. Think about this.
(20 Nov '17, 03:20)
@nilesh3105 yes, the one of the methods in the bithacks link does exactly that :D @likecs I didn't know that, thanks! Although according to the source here,
(20 Nov '17, 03:29)
@likecs __builtin prefixed functions translate directly to the appropriate assembly instruction(s). Provided the processor has them. __lg() function is a wrapper function. Maybe when i get time i will analyze assembler output for different implementations.
(20 Nov '17, 03:45)
(22 Nov '17, 18:11)

Anyone know how to fix \underbrace latex here?
What needs fixing? Looks good to me!
Very well written tutorial! Great work
@meooow I replaced it with an image. lets see if it works here $\underbrace{m_1m_2m_3m_4m_5 \ldots m_k}*{\text{binary representation of j}}1\underbrace{00000 \ldots0 0000}*{xi1 \text{ zeroes}}$
@adhyyan1252 Thank you!
Oh I didn't notice it was an image. I messed around with the formatting and apparently if you have more than one underbrace on the same line it shows up incorrectly like that. But you can avoid it, just put spaces before and after the underscore like this:
\underbrace{abc} _ {def} ghi \underbrace{jkl} _ {mno}
becomes $\underbrace{abc} _ {def} ghi \underbrace{jkl} _ {mno}$Thanks. Fixed.