Disjoint Sparse Table

Disjoint Sparse Data Structure

The structure of a disjoint sparse table is very similar to that of a segment tree.

We'll presume that the given array has already been resized to a size that is a power of two. The levels in a disjoint sparse table are numbered from 0 to log N. At any ‘i’th level, we partition the array into 2 * i blocks. We keep the operation total of elements between any index in the block and the middle of the block for each block. 

If we talk about its specific structure, then Level 0 would have one block whose middle will be N / 2,  whereas level 1 would have two blocks, one with a middle of N/4 and the other with a middle of 3 * N / 4 and so on. At each block, we will store the operational sum of elements between any index in the block and the middle of the block.

Here, we have taken the example sum queries question where we have to print the sum in a particular range.

Shown below is its structure in action.

Structure of Disjoint Sparse Table

But how are we gonna implement it?

To get the sum of elements in a given range, let’s say [L, R], we simply need to locate the block that contains both 'L' and 'R'.

Let’s take an example to understand this better.

Let’s say we have a disjoint sparse table with 7 levels and 2 ^ 7 elements, the binary representations of L and R are (using seven bits for each index) just for example:

L : 1101[0]01

R :  1101[1]10

The 4th bit (0-indexed) from the left, marked in square brackets, is the leftmost position where the bits differ. As a result, the block's middle element will be 1101100. The level including this block is 4 since the 4th bit differs. For this block, the element range is [1101000,1101111]. We simply need to add two table components, sum[level][L], which is the sum of [L, MID], and sum[level][R], which is the sum of [MID, R]. Here sum is the disjoint sparse table in the form of an array

So all we have to do now is find the level, which is the difference in the position of the leftmost bit. The leftmost 1 in L^R = 0000111 is simply this. We may detect this using the GCC extension  __builtin clz(x), which counts the number of leading zeros in the integer x.

Once we have the level, we can easily compute any of the queries.

Frequently Asked Questions

1. What is a sparse table?
   Sparse table is the 2-dimensional array say, SPARSE[N][16] where SPARSE[i][j] stores the result from ith index to (i + 2 ^ j )th index.
    
2. What is the time complexity to create a sparse table?
   Creating a sparse table takes O(N*log(M)) where ‘M’ is the maximum element in the array and N is the size of the array.
    
3. What do you mean by an algorithm?
   An algorithm is a step-by-step procedure for solving a problem. It is not required to write the algorithm in any programming language but simple English can also be used to write an algorithm.
    
4. How is the performance of an algorithm measured?
   To measure the performance of an algorithm and to compare two algorithms, we use the time and the space complexities of the algorithm.
    
5. What is a disjoin sparse table?
   The disjoint sparse table data structure is the advanced form of a sparse table which may perform every type of query in O(1) space and O(N * log (N)) time complexity. 

Key Takeaways

We saw and learned about this new data structure called Disjoint sparse table and saw how it could solve the problem in less time and space as compared to sparse tables. 

Now, this was just the beginning of your journey to becoming a star coder. Thus it’s time to move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems, read interview experiences, and many more. 

Till then, Happy Coding!