Prefix Sums

The simplest technique for range sum queries in static arrays:

#include <vector>

class PrefixSum {
private:
    vector<long long> prefix;
    
public:
    PrefixSum(const vector<int>& arr) {
        int n = arr.size();
        prefix.resize(n + 1, 0);
        
        // Build prefix sum array
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
    }
    
    // Query sum from index l to r (inclusive)
    long long rangeSum(int l, int r) {
        return prefix[r + 1] - prefix[l];
    }
};

int main() {
    vector<int> arr = {2, 4, 3, 1, 6, 9, 7};
    PrefixSum ps(arr);
    
    // Query examples
    cout << "Sum [1,3]: " << ps.rangeSum(1, 3) << endl; // 4+3+1 = 8
    cout << "Sum [2,5]: " << ps.rangeSum(2, 5) << endl; // 3+1+6+9 = 19
    
    return 0;
}
                    

2D Prefix Sums

Extend prefix sums to handle 2D range queries:

class PrefixSum2D {
private:
    vector<vector<long long>> prefix;
    
public:
    PrefixSum2D(const vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        prefix.resize(rows + 1, vector<long long>(cols + 1, 0));
        
        // Build 2D prefix sum
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefix[i][j] = matrix[i-1][j-1] 
                             + prefix[i-1][j] 
                             + prefix[i][j-1] 
                             - prefix[i-1][j-1];
            }
        }
    }
    
    // Query sum of rectangle from (r1,c1) to (r2,c2)
    long long rangeSum(int r1, int c1, int r2, int c2) {
        return prefix[r2+1][c2+1] 
             - prefix[r1][c2+1] 
             - prefix[r2+1][c1] 
             + prefix[r1][c1];
    }
};
                    

Binary Indexed Tree (Fenwick Tree)

Efficient data structure for range sum queries with updates:

class BinaryIndexedTree {
private:
    vector<long long> tree;
    int n;
    
public:
    BinaryIndexedTree(int size) : n(size) {
        tree.resize(n + 1, 0);
    }
    
    BinaryIndexedTree(const vector<int>& arr) : n(arr.size()) {
        tree.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            update(i, arr[i]);
        }
    }
    
    // Add val to index i
    void update(int i, int val) {
        for (++i; i <= n; i += i & -i) {
            tree[i] += val;
        }
    }
    
    // Get prefix sum up to index i
    long long query(int i) {
        long long sum = 0;
        for (++i; i > 0; i -= i & -i) {
            sum += tree[i];
        }
        return sum;
    }
    
    // Get range sum from l to r
    long long rangeQuery(int l, int r) {
        return query(r) - (l > 0 ? query(l - 1) : 0);
    }
};

int main() {
    vector<int> arr = {2, 4, 3, 1, 6, 9, 7};
    BinaryIndexedTree bit(arr);
    
    cout << "Sum [1,3]: " << bit.rangeQuery(1, 3) << endl; // 8
    
    bit.update(2, 5); // Add 5 to index 2
    cout << "Sum [1,3] after update: " << bit.rangeQuery(1, 3) << endl; // 13
    
    return 0;
}
                    

Segment Tree

Versatile data structure for various range queries:

class SegmentTree {
private:
    vector<long long> tree;
    vector<int> arr;
    int n;
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int 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];
        }
    }
    
    void updateHelper(int node, int start, int end, int idx, int val) {
        if (start == end) {
            arr[idx] = val;
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                updateHelper(2 * node, start, mid, idx, val);
            } else {
                updateHelper(2 * node + 1, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
    
    long long queryHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0; // Outside range
        }
        if (l <= start && end <= r) {
            return tree[node]; // Completely inside range
        }
        
        int mid = (start + end) / 2;
        long long p1 = queryHelper(2 * node, start, mid, l, r);
        long long p2 = queryHelper(2 * node + 1, mid + 1, end, l, r);
        return p1 + p2;
    }
    
public:
    SegmentTree(const vector<int>& inputArr) {
        arr = inputArr;
        n = arr.size();
        tree.resize(4 * n);
        build(1, 0, n - 1);
    }
    
    void update(int idx, int val) {
        updateHelper(1, 0, n - 1, idx, val);
    }
    
    long long query(int l, int r) {
        return queryHelper(1, 0, n - 1, l, r);
    }
};
                    

Range Minimum Query (RMQ)

Find the minimum element in any range efficiently:

class RMQSegmentTree {
private:
    vector<int> tree;
    vector<int> arr;
    int n;
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node, start, mid);
            build(2 * node + 1, mid + 1, end);
            tree[node] = min(tree[2 * node], tree[2 * node + 1]);
        }
    }
    
    int queryHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return INT_MAX; // Outside range
        }
        if (l <= start && end <= r) {
            return tree[node]; // Completely inside range
        }
        
        int mid = (start + end) / 2;
        int p1 = queryHelper(2 * node, start, mid, l, r);
        int p2 = queryHelper(2 * node + 1, mid + 1, end, l, r);
        return min(p1, p2);
    }
    
public:
    RMQSegmentTree(const vector<int>& inputArr) {
        arr = inputArr;
        n = arr.size();
        tree.resize(4 * n);
        build(1, 0, n - 1);
    }
    
    int query(int l, int r) {
        return queryHelper(1, 0, n - 1, l, r);
    }
};
                    

Sparse Table (Static RMQ)

O(1) query time for static range minimum queries:

class SparseTable {
private:
    vector<vector<int>> st;
    vector<int> logs;
    
public:
    SparseTable(const vector<int>& arr) {
        int n = arr.size();
        int maxLog = 0;
        while ((1 << maxLog) <= n) maxLog++;
        
        st.resize(maxLog, vector<int>(n));
        logs.resize(n + 1);
        
        // Precompute logs
        logs[1] = 0;
        for (int i = 2; i <= n; i++) {
            logs[i] = logs[i / 2] + 1;
        }
        
        // Initialize for length 1
        for (int i = 0; i < n; i++) {
            st[0][i] = arr[i];
        }
        
        // Fill sparse table
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
            }
        }
    }
    
    int query(int l, int r) {
        int j = logs[r - l + 1];
        return min(st[j][l], st[j][r - (1 << j) + 1]);
    }
};
                    

Performance Comparison