Static Range Sum Queries

Given an array of n integers, your task is to process q queries of the form: what is the sum of values in the range [a,b]?

Example:

Input:  n = 8, q = 4, v = {3, 2, 4, 5, 1, 1, 5, 3}, queries = {{2, 4}, {5, 6}, {1, 8}, {3, 3}}

Output:

11
2
24
4

Approach 1: Using Sparse Table Data Structure 

C++

#include <bits/stdc++.h>
using namespace std;
long long int arr[1000001];
#define MAXN 1000001
#define K 25
long long int st[MAXN][K + 1];

void init(long long int n)
{
    for (long long int i = 0; i < n; i++)
        st[i][0] = arr[i];
    for (long long int j = 1; j <= K; j++)
    {
        for (long long int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = st[i][j - 1] +
                       st[i + (1 << (j - 1))][j - 1];
    }
}
long long int query(long long int l, long long int r)
{
    long long int sum = 0;
    for (long long int j = K; j >= 0; j--)
    {
        if ((1 << j) <= r - l + 1)
        {
            sum += st[l][j];
            l += 1 << j;
        }
    }
    return sum;
}
int main()
{
    long long int n = 8;
    long long int q = 4;

    vector<int> v = {3, 2, 4, 5, 1, 1, 5, 3};

    vector<vector<long long int>> queries = {{2, 4},
                                             {5, 6},
                                             {1, 8},
                                             {3, 3}};
    for (long long int i = 0; i < n; i++)
        arr[i] = v[i];
    init(n);

    for (int i = 0; i < q; i++)
    {
        long long int l = queries[i][0];
        long long int r = queries[i][1];

        l--;
        r--;
        cout << query(l, r) << "\n";
    }
    return 0;
}

Approach 2: Using Segment Tree Data structure

C++

#include <bits/stdc++.h>
using namespace std;
long long arr[1000001];
long long tree[4010001];
void build(long long node,
           long long start, long long end)
{
    if (start == end)
    {
        tree[node] = arr[start];
        return;
    }
    long long mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
long long query(long long node, long long start,
                long long end, long long l, long long r)
{
    if (r < start || l > end)
        return 0;
    if (l <= start && r >= end)
        return tree[node];
    long long mid = (start + end) / 2;
    long long p1 = query(2 * node, start, mid, l, r);
    long long p2 = query(2 * node + 1, mid + 1, end, l, r);
    return p1 + p2;
}
int main()
{
    long long int n = 8;
    long long int q = 4;

    vector<int> v = {3, 2, 4, 5, 1, 1, 5, 3};

    vector<vector<long long int>> queries = {{2, 4},
                                             {5, 6},
                                             {1, 8},
                                             {3, 3}};
    for (long long int i = 1; i <= n; i++)
        arr[i] = v[i - 1];
    build(1, 1, n);

    for (int i = 0; i < q; i++)
    {
        long long int l = queries[i][0];
        long long int r = queries[i][1];

        cout << query(1, 1, n, l, r) << "\n";
    }
    return 0;
}