Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Range Sum Query in Linear Time
public class RSQLog
{
private int[] A;
private int[,] sparseTable;
private int[] logTable;
public RSQLog(int[] A)
{
this.PrecomputeSparseTable(A);
}
public int RSQ(int left, int right)
{
var sum = 0;
// The size of the second dimension
var K = sparseTable.GetLength(1);
for (int j = K; j >= 0; j--)
{
if ((1 << j) <= (right - left + 1))
{
sum += this.sparseTable[left, j];
left += 1 << j;
}
}
return sum;
}
private void PrecomputeSparseTable(int[] A)
{
var N = A.Length;
this.logTable = new int[N + 1];
this.logTable[0] = -1;
for (int i = 1; i <= N; i++)
this.logTable[i] = this.logTable[i / 2] + 1;
var K = this.logTable[N];
this.sparseTable = new int[N, K + 1];
this.A = A;
// Initial step
for (int i = 0; i < N; i++)
sparseTable[i, 0] = A[i];
// Iteration
for (int j = 1; j <= K; j++)
{
for (int i = 0; i + (1 << j) <= N; i++)
{
int left = sparseTable[i, j - 1];
int right = sparseTable[i + (1 << (j - 1)), j - 1];
sparseTable[i, j] = left + right;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.