Difference Arrays & Doubling

Difference arrays and doubling algorithms are powerful techniques for range operations and tree queries. This section covers 1D/multi-dimensional difference arrays, Sparse Table (ST) for range minimum queries, and binary lifting for Lowest Common Ancestor (LCA) problems.

Difference Arrays

Difference arrays enable efficient range updates in O(1) time by storing differences between consecutive elements.

1D and 2D Difference Arrays

#include <iostream>
#include <vector>
using namespace std;

class DifferenceArray1D {
private:
    vector<long long> diff;
    int n;
    
public:
    DifferenceArray1D(vector<int>& arr) : n(arr.size()) {
        diff.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            diff[i] += arr[i];
            diff[i + 1] -= arr[i];
        }
    }
    
    // Add value to range [l, r]
    void rangeAdd(int l, int r, int value) {
        diff[l] += value;
        if (r + 1 <= n) {
            diff[r + 1] -= value;
        }
    }
    
    // Get final array after all updates
    vector<long long> getArray() {
        vector<long long> result(n);
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
};

class DifferenceArray2D {
private:
    vector<vector<long long>> diff;
    int rows, cols;
    
public:
    DifferenceArray2D(int r, int c) : rows(r), cols(c) {
        diff.assign(r + 1, vector<long long>(c + 1, 0));
    }
    
    // Add value to rectangle [r1,c1] to [r2,c2]
    void rangeAdd(int r1, int c1, int r2, int c2, int value) {
        diff[r1][c1] += value;
        diff[r1][c2 + 1] -= value;
        diff[r2 + 1][c1] -= value;
        diff[r2 + 1][c2 + 1] += value;
    }
    
    // Get final 2D array
    vector<vector<long long>> getArray() {
        vector<vector<long long>> result(rows, vector<long long>(cols));
        
        // Compute prefix sums
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                result[i][j] = diff[i][j];
                if (i > 0) result[i][j] += result[i-1][j];
                if (j > 0) result[i][j] += result[i][j-1];
                if (i > 0 && j > 0) result[i][j] -= result[i-1][j-1];
            }
        }
        
        return result;
    }
};

int main() {
    // Test 1D difference array
    cout << "1D Difference Array Test:" << endl;
    vector<int> arr = {1, 2, 3, 4, 5};
    DifferenceArray1D diff1d(arr);
    
    diff1d.rangeAdd(1, 3, 10);  // Add 10 to indices 1-3
    diff1d.rangeAdd(0, 2, 5);   // Add 5 to indices 0-2
    
    vector<long long> result1d = diff1d.getArray();
    cout << "Result: ";
    for (long long x : result1d) cout << x << " ";
    cout << endl;
    
    // Test 2D difference array
    cout << "\n2D Difference Array Test:" << endl;
    DifferenceArray2D diff2d(3, 3);
    
    diff2d.rangeAdd(0, 0, 1, 1, 5);  // Add 5 to 2x2 rectangle
    diff2d.rangeAdd(1, 1, 2, 2, 3);  // Add 3 to 2x2 rectangle
    
    vector<vector<long long>> result2d = diff2d.getArray();
    cout << "Result:" << endl;
    for (auto& row : result2d) {
        for (long long x : row) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

Difference arrays convert range updates to point updates. 1D version uses diff[l] += val, diff[r+1] -= val. 2D version uses inclusion-exclusion principle for rectangle updates.

Sparse Table (ST) for Range Minimum Queries

Sparse Table uses binary lifting to answer range minimum queries in O(1) time with O(n log n) preprocessing.

Sparse Table Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class SparseTable {
private:
    vector<vector<int>> st;
    vector<int> logs;
    int n;
    
public:
    SparseTable(vector<int>& arr) : n(arr.size()) {
        int maxLog = log2(n) + 1;
        st.assign(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 first level
        for (int i = 0; i < n; i++) {
            st[0][i] = arr[i];
        }
        
        // Build sparse table
        for (int k = 1; k < maxLog; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]);
            }
        }
    }
    
    // Query minimum in range [l, r]
    int query(int l, int r) {
        int k = logs[r - l + 1];
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

// Binary Lifting for LCA
class LCA {
private:
    vector<vector<int>> up;
    vector<int> depth;
    int n, LOG;
    
    void dfs(int v, int p, const vector<vector<int>>& adj) {
        up[0][v] = p;
        for (int i = 1; i < LOG; i++) {
            up[i][v] = up[i-1][up[i-1][v]];
        }
        
        for (int u : adj[v]) {
            if (u != p) {
                depth[u] = depth[v] + 1;
                dfs(u, v, adj);
            }
        }
    }
    
public:
    LCA(int vertices, vector<vector<int>>& adj, int root = 0) : n(vertices) {
        LOG = ceil(log2(n)) + 1;
        up.assign(LOG, vector<int>(n));
        depth.assign(n, 0);
        
        dfs(root, root, adj);
    }
    
    int lca(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        
        // Bring a to same level as b
        int diff = depth[a] - depth[b];
        for (int i = 0; i < LOG; i++) {
            if ((diff >> i) & 1) {
                a = up[i][a];
            }
        }
        
        if (a == b) return a;
        
        // Binary lifting to find LCA
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[i][a] != up[i][b]) {
                a = up[i][a];
                b = up[i][b];
            }
        }
        
        return up[0][a];
    }
    
    int distance(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }
};

int main() {
    // Test Sparse Table
    cout << "Sparse Table Test:" << endl;
    vector<int> arr = {7, 2, 3, 0, 5, 10, 3, 12, 18};
    SparseTable st(arr);
    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "RMQ(1, 4) = " << st.query(1, 4) << endl;
    cout << "RMQ(0, 8) = " << st.query(0, 8) << endl;
    cout << "RMQ(3, 6) = " << st.query(3, 6) << endl;
    
    // Test LCA
    cout << "\nLCA Test:" << endl;
    vector<vector<int>> tree(7);
    tree[0] = {1, 2};
    tree[1] = {0, 3, 4};
    tree[2] = {0, 5, 6};
    tree[3] = {1};
    tree[4] = {1};
    tree[5] = {2};
    tree[6] = {2};
    
    LCA lca(7, tree, 0);
    
    cout << "LCA(3, 4) = " << lca.lca(3, 4) << endl;
    cout << "LCA(3, 5) = " << lca.lca(3, 5) << endl;
    cout << "Distance(3, 5) = " << lca.distance(3, 5) << endl;
    
    return 0;
}

Sparse Table uses the fact that any range can be covered by two overlapping powers of 2. LCA uses binary lifting to jump up the tree efficiently, preprocessing all 2^k ancestors.