# Range sum query using Sparse Table

We have an array arr[]. We need to find the sum of all the elements in the range L and R where 0 <= L <= R <= n-1. Consider a situation when there are many range queries.

Examples:

```Input : 3 7 2 5 8 9
query(0, 5)
query(3, 5)
query(2, 4)
Output : 34
22
15

Note : array is 0 based indexed
and queries too.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Since there are no updates/modifications, we use Sparse table to answer queries efficiently. In sparse table, we break queries in powers of 2.

```Suppose we are asked to compute sum of
elements from arr[i] to arr[i+12].
We do the following:

// Use sum of 8 (or 23) elements
table[i][3] = sum(arr[i], arr[i + 1], ...
arr[i + 7]).

// Use sum of 4 elements
table[i+8][2] = sum(arr[i+8], arr[i+9], ..
arr[i+11]).

// Use sum of single element
table[i + 12][0] = sum(arr[i + 12]).

Our result is sum of above values.```

Notice that it took only 4 actions to compute result over subarray of size 13.

## C++

 `// CPP program to find the sum in a given ` `// range in an array using sparse table. ` `#include ` `using` `namespace` `std; ` ` `  `// Because 2^17 is larger than 10^5 ` `const` `int` `k = 16; ` ` `  `// Maximum value of array ` `const` `int` `N = 1e5; ` ` `  `// k + 1 because we need to access ` `// table[r][k] ` `long` `long` `table[N][k + 1]; ` ` `  `// it builds sparse table. ` `void` `buildSparseTable(``int` `arr[], ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``table[i][0] = arr[i]; ` ` `  `    ``for` `(``int` `j = 1; j <= k; j++) ` `        ``for` `(``int` `i = 0; i <= n - (1 << j); i++) ` `            ``table[i][j] = table[i][j - 1] + ` `               ``table[i + (1 << (j - 1))][j - 1]; ` `} ` ` `  `// Returns the sum of the elements in the range ` `// L and R. ` `long` `long` `query(``int` `L, ``int` `R) ` `{ ` `    ``// boundaries of next query, 0-indexed ` `    ``long` `long` `answer = 0; ` `    ``for` `(``int` `j = k; j >= 0; j--) { ` `        ``if` `(L + (1 << j) - 1 <= R) { ` `            ``answer = answer + table[L][j]; ` ` `  `            ``// instead of having L', we ` `            ``// increment L directly ` `            ``L += 1 << j; ` `        ``} ` `    ``} ` `    ``return` `answer; ` `} ` ` `  `// Driver program. ` `int` `main() ` `{ ` `    ``int` `arr[] = { 3, 7, 2, 5, 8, 9 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` ` `  `    ``buildSparseTable(arr, n); ` ` `  `    ``cout << query(0, 5) << endl; ` `    ``cout << query(3, 5) << endl; ` `    ``cout << query(2, 4) << endl; ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to find the sum  ` `// in a given range in an array  ` `// using sparse table. ` `class` `GFG ` `{ ` `     `  `// Because 2^17 is larger than 10^5 ` `static` `int` `k = ``16``; ` ` `  `// Maximum value of array ` `static` `int` `N = ``100000``; ` ` `  `// k + 1 because we need ` `// to access table[r][k] ` `static` `long` `table[][] = ``new` `long``[N][k + ``1``]; ` ` `  `// it builds sparse table. ` `static` `void` `buildSparseTable(``int` `arr[], ` `                             ``int` `n) ` `{ ` `    ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``table[i][``0``] = arr[i]; ` ` `  `    ``for` `(``int` `j = ``1``; j <= k; j++) ` `        ``for` `(``int` `i = ``0``; i <= n - (``1` `<< j); i++) ` `            ``table[i][j] = table[i][j - ``1``] + ` `            ``table[i + (``1` `<< (j - ``1``))][j - ``1``]; ` `} ` ` `  `// Returns the sum of the  ` `// elements in the range L and R. ` `static` `long` `query(``int` `L, ``int` `R) ` `{ ` `    ``// boundaries of next query, ` `    ``// 0-indexed ` `    ``long` `answer = ``0``; ` `    ``for` `(``int` `j = k; j >= ``0``; j--)  ` `    ``{ ` `        ``if` `(L + (``1` `<< j) - ``1` `<= R)  ` `        ``{ ` `            ``answer = answer + table[L][j]; ` ` `  `            ``// instead of having L', we ` `            ``// increment L directly ` `            ``L += ``1` `<< j; ` `        ``} ` `    ``} ` `    ``return` `answer; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{ ` `    ``int` `arr[] = { ``3``, ``7``, ``2``, ``5``, ``8``, ``9` `}; ` `    ``int` `n = arr.length; ` ` `  `    ``buildSparseTable(arr, n); ` ` `  `    ``System.out.println(query(``0``, ``5``)); ` `    ``System.out.println(query(``3``, ``5``)); ` `    ``System.out.println(query(``2``, ``4``)); ` `} ` `} ` ` `  `// This code is contributed  ` `// by Kirti_Mangal `

## C#

 `// C# program to find the  ` `// sum in a given range ` `// in an array using ` `// sparse table. ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Because 2^17 is ` `    ``// larger than 10^5 ` `    ``static` `int` `k = 16; ` `     `  `    ``// Maximum value  ` `    ``// of array ` `    ``static` `int` `N = 100000; ` `     `  `    ``// k + 1 because we  ` `    ``// need to access table[r,k] ` `    ``static` `long` `[,]table =  ` `           ``new` `long``[N, k + 1]; ` `     `  `    ``// it builds sparse table. ` `    ``static` `void` `buildSparseTable(``int` `[]arr,  ` `                                 ``int` `n) ` `    ``{ ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``table[i, 0] = arr[i]; ` `     `  `        ``for` `(``int` `j = 1; j <= k; j++) ` `            ``for` `(``int` `i = 0;      ` `                     ``i <= n - (1 << j); i++) ` `                ``table[i, j] = table[i, j - 1] + ` `                ``table[i + (1 << (j - 1)), j - 1]; ` `    ``}      ` `     `  `    ``// Returns the sum of the ` `    ``// elements in the range ` `    ``// L and R. ` `    ``static` `long` `query(``int` `L, ``int` `R) ` `    ``{ ` `        ``// boundaries of next  ` `        ``// query, 0-indexed ` `        ``long` `answer = 0; ` `        ``for` `(``int` `j = k; j >= 0; j--)  ` `        ``{ ` `            ``if` `(L + (1 << j) - 1 <= R)  ` `            ``{ ` `                ``answer = answer +  ` `                         ``table[L, j]; ` `     `  `                ``// instead of having  ` `                ``// L', we increment  ` `                ``// L directly ` `                ``L += 1 << j; ` `            ``} ` `        ``} ` `        ``return` `answer; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = ``new` `int``[]{3, 7, 2,  ` `                              ``5, 8, 9}; ` `        ``int` `n = arr.Length; ` `     `  `        ``buildSparseTable(arr, n); ` `     `  `        ``Console.WriteLine(query(0, 5)); ` `        ``Console.WriteLine(query(3, 5)); ` `        ``Console.WriteLine(query(2, 4)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

Output:

```34
22
15
```

This algorithm for answering queries with Sparse Table works in O(k), which is O(log(n)), because we choose minimal k such that 2^k+1 > n.

Time complexity of sparse table construction : Outer loop runs in O(k), inner loop runs in O(n). Thus, in total we get O(n * k) = O(n * log(n))