#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];
        }
    }
    
    // 在区间[l, r]上加上value
    void rangeAdd(int l, int r, int value) {
        diff[l] += value;
        if (r + 1 <= n) {
            diff[r + 1] -= value;
        }
    }
    
    // 获取所有更新后的最终数组
    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));
    }
    
    // 在矩形[r1,c1]到[r2,c2]上加上value
    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;
    }
    
    // 获取最终二维数组
    vector<vector<long long>> getArray() {
        vector<vector<long long>> result(rows, vector<long long>(cols));
        
        // 计算前缀和
        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() {
    // 测试一维差分数组
    cout << "一维差分数组测试：" << endl;
    vector<int> arr = {1, 2, 3, 4, 5};
    DifferenceArray1D diff1d(arr);
    
    diff1d.rangeAdd(1, 3, 10);  // 在索引1-3上加10
    diff1d.rangeAdd(0, 2, 5);   // 在索引0-2上加5
    
    vector<long long> result1d = diff1d.getArray();
    cout << "结果：";
    for (long long x : result1d) cout << x << " ";
    cout << endl;
    
    // 测试二维差分数组
    cout << "\n二维差分数组测试：" << endl;
    DifferenceArray2D diff2d(3, 3);
    
    diff2d.rangeAdd(0, 0, 1, 1, 5);  // 在2x2矩形上加5
    diff2d.rangeAdd(1, 1, 2, 2, 3);  // 在2x2矩形上加3
    
    vector<vector<long long>> result2d = diff2d.getArray();
    cout << "结果：" << endl;
    for (auto& row : result2d) {
        for (long long x : row) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

#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);
        
        // 预计算对数
        logs[1] = 0;
        for (int i = 2; i <= n; i++) {
            logs[i] = logs[i / 2] + 1;
        }
        
        // 初始化第一层
        for (int i = 0; i < n; i++) {
            st[0][i] = arr[i];
        }
        
        // 构建稀疏表
        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))]);
            }
        }
    }
    
    // 查询区间[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]);
    }
};

// 二进制提升求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);
        
        // 将a提升到与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;
        
        // 二进制提升找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() {
    // 测试稀疏表
    cout << "稀疏表测试：" << endl;
    vector<int> arr = {7, 2, 3, 0, 5, 10, 3, 12, 18};
    SparseTable st(arr);
    
    cout << "数组：";
    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;
    
    // 测试LCA
    cout << "\nLCA测试：" << 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 << "距离(3, 5) = " << lca.distance(3, 5) << endl;
    
    return 0;
}