Square Root Decomposition.

squareRootDecomposition.cpp

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

/*
	Square Root Decomposition is used for "Range Querying" with the Time Complexity of O(sqrt(n)).
	We Decompose the array into 'ceil(sqrt(n))' blocks. We calculate the result for each Block and store them.
	
	When Updating (given the index), we change the value at that index to the new value. We also have to
	update Block's result.
	
	While Querying,
		- Partial left elements are queried. (Elements partially lying left to the completely overlapping Blocks.)
		- Completely Overlapped Blocks. (All elements in the block are to be queried.)
		- Partial right elements are queried. (Elements partially lying right to the completely overlapping Blocks.)
		
	So, sqrt(n) for every block ie, O(3 * sqrt(n)) which is O(sqrt(n)).
	
	Time Complexities:
	Build()  -> O(n) // One-Time Process.
	Update() -> O(1)
	Query()  -> O(sqrt(n))
*/

// Initialize Global Variables.
int *Block, *a;
int blockIndex = -1, blockSize;

// Display Whole Array.
void Disp(int n) {
	for (int t=0;t<n;t++)
		cout << a[t] << " ";

	cout << endl;
	return;
}

// Initialize Block Elements.
void initializeBlocks(int *Block, int blockSize) {
	for (int t=0;t<blockSize;t++)
		Block[t] = 0;

	return;
}

// Query Array.
int Query(int l, int r) {
	int sum = 0;

	while ((l % blockSize != 0) && (l != 0) && (l < r)) {
		sum += a[l];
		++l;
	}

	while ((l + blockSize) <= r) {
		sum += Block[l/blockSize];
		l += blockSize;
	}

	while (l <= r) {
		sum += a[l];
		++l;
	}
	return sum;
}

// Update Array Element at Index.
void Update(int index, int newValue) {
	int blockNumber = (index % blockSize);
	a[index] = newValue;
	Block[blockNumber] += a[index] - newValue;
	return;
}

// Build Blocks.
void Build_(int n) {
	blockSize = ceil(sqrt(n));

	Block = new int[blockSize];
	initializeBlocks(Block, blockSize);

	for (int t=0;t<n;t++) {
		if (t % blockSize == 0)
			++blockIndex;

		Block[blockIndex] += a[t];
	}
	return;
}

/*
int main() {
	int ar[] = {1, 5, 2, 4, 6, 1, 3, 5, 7, 10};
	a = ar;
	Build_(10);
	Query(0, 3);

	Disp(10);
	Update(0, 33);
	Query(0, 3);
	Disp(10);
}
*/