Decompositions - RahulKushwaha/Algorithms GitHub Wiki

It is basically a pattern to decompose a problem in smaller parts which can be easily solved. Here the size of decomposition is equal to sqrt(n), where n is the size of the input.

Let us understand this with the help of an example: input = [1, 2, 3, 4, 5, 6, 7]

And we have a list of functions like: Max, Min, etc,. Let's denote the functions by f(x, y) where x and y are the indices of the input array.

y = f(x, y)

Naive Method:

Query: f(i, j)

We can iterate from index i to j to find the value.

// We should initialize the value of the result with some good sentinel value.
int result = input[i];
for(int a = i; a <= j; a ++){
	result = f(input[a], result);
}

Time Complexity: O(n)

There are many ways we can improve the query time. The fundamental idea behind is to percompute the results of the different segments of the input array. The size of the segment and overlap between different segments ultimately contributes to the final space and time complextiy.

Square Root Decomposition:

Here we divide the input into segments equal to sqrt(n) and there are sqrt(n) segments where n is the size of the input.

Applying Square Root Decomposition to the above input example: n = 7 d = sqrt(n) = 2 (floor)

After dividing the input into d segments of size d we have the following result:

lookup[i] = the value of the function for indices i to i + d
lookup[1] = Min(input[1], input[2], input[3])
lookup[2] = Min(input[4], input[5], input[6])
.
.
lookup[n] = Min(input[n - 2], input[n - 1], input[n])

Therefore to evaluate the function, Min(i, j), we can say

Min(i, j) = Min(lookup[i], lookup[i + 1], lookup[i + 2], ..., lookup[i + k]])
where i + k + d < j

If j - i < d, then we can go through all the elements in the range to find the Min value, O(d). If (j - i) == n, then we have to go through at most d segments.

However, there is a caveat. It is possible that the boundary segments may not completely align with the segment size. 'i' and 'j' point to a location somewhere inside the block. In those cases we cannot use the lookup table. Rather, we wil have to compute the value of the function using the naive method in those two blocks and for rest of the blocks that lie between i and j we can use the lookup table.

For example: Query = Min(3, 97), n = 5 Min(3, 97) = Minimun(Min(3, 5), lookup[2], lookup[3], ... , lookup[18], Min(95, 97) Every query can be decomposed into combination of queries consisting of at most 2 partial segments and a number of full segments.

In this case the first segment, lookup[1], contains two extra elements, input[1] and input[2], and therefore cannot be used. To counter this problem we ignore the first segment and go thourgh all the elements in the input from i to (floor(i / d) * d + d). The same can be said about the end segment when j does not align completely with the ending segments.

Query = Min(i, j)

Starting Segment = (floor(i / d) * d)  == i ? floor(i / d) : floor(i / d) + 1
Here we have ignored the segment, lookup[floor(i / d)] if contains elements less than i.

Last Segment = (floor(j / d) * d + d) == j ? floor(j / d) : floor(j / d) - 1
Ignore the last segment if it contains greater than j.

Space Complexity: O(sqrt n)

Query Time Complexity: O(sqrt n) + 2 * O(sqrt n) = O(sqrt n)

class RMQ {
private:
	int blocks[SIZE];
	int size;

public:
	RMQ(int n) : size(ceil(sqrt(n))) {

		for (int i = 0; i <= size; i++) {
			int answer = INT_MAX;
			int limit = i * size + size;
			for (int j = i * size; j < limit && j < n; j++) {
				answer = min(answer, input[j]);
			}

			blocks[i] = answer;
		}
	}

	int query(int l, int r) {
		int answer = input[l];
		int leftIndex = l / size, rightIndex = r / size;

		if (l != leftIndex * size) {
			int limit = leftIndex * size + size;
			for (int i = l; i < limit && i <= r; i++) {
				answer = min(answer, input[i]);
			}

			leftIndex++;
		}

		if (rightIndex * size + size - 1 != r) {
			for (int i = max(rightIndex * size, l); i <= r; i++) {
				answer = min(answer, input[i]);
			}

			rightIndex--;
		}

		for (int i = leftIndex; i <= rightIndex; i++) {
			answer = min(blocks[i], answer);
		}

		return answer;
	}
};

MO Algorithm

There is another way we can apply the decomposition. If the problem involves offline queries, queries which do not modify the input and therefore can be rearranged before answering, we can apply sqrt decomposition to the queries. We can collect all the queries and sort them in a manner that allows for reducing the overall time complexity.

Let us borrow the structure of query from above

Query = f(x, y)
Where f can be a variety of functions like: Min, Max, Sum, etc,.

After getting all the queries in a single collection we can divide them into blocks. The left index, x or i, is used to get the block index and all the queries inside a block are sorted according to the right index, y or j.

Therefore to solve all the queries of block we will be moving the right index by at most n, as they are all sorted, and the left index by at most Q where Q is the total number of queries.

Let us denote sqrt(n) by k.
Time Complexity for a block: O(Q * k + n)
Time Complexity: O(k * (Q * k + n)) = O(kQ + k^2 + kn) = O(kQ + n + kn) = O(k*(Q + n))

Sparse Table:

Here is another decomposition where we divide the input array in overlapping segments each of size 2^j, 0 <= j <= log(n). Let us denote all the segments as lookup[i][j]

lookup[i][j] = f(input[i], ..., input[i + 2^j - 1])

For example:

int p = log2(j - i + 1);
Min(i, j) = Minimum(lookup[i][p], lookup[j - pow(2, j) + 1][p])

Min(2, 10) = Minimum(lookup[2][3], lookup[3][10])
lookup[2][3] and lookup[3][10] cover the whole input required by i and j.

Min Query Time Complexity: O(1)

For problems which can be answered by overlapping segements, eg. Min, Max.., the query time will be constant. Problems which require disjoint segments, eg. Sum, will be solved in O(lg n) time.

Sum Query:

Sum(2, 11) = Sum(2, 9) + sum(10, 11)
which can be translated to 
Sum(2, 11) = lookup[2][3] + lookup[10][1]

Time Complexity:

    Query Time: O(1) [Overlapping Segments], O(lg n) [Disjoint Segment]
    Space Complexity: O(n lg n)