线段树

掌握线段树进行高效的区间查询和更新。学习构建、点/区间更新、懒惰传播和竞赛编程中的高级应用。

1. 基础线段树

用于区间和查询和点更新的线段树，时间复杂度为 O(log n)。

基础线段树实现

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

class SegmentTree {
private:
    vector<long long> tree;
    int n;
    
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 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) {
            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]; // Complete overlap
        }
        
        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(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 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);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegmentTree st(arr);
    
    cout << "Original array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    // Range queries
    cout << "Sum of range [1, 3]: " << st.query(1, 3) << endl;
    cout << "Sum of range [2, 5]: " << st.query(2, 5) << endl;
    
    // Point update
    st.update(1, 10);
    cout << "After updating index 1 to 10:" << endl;
    cout << "Sum of range [1, 3]: " << st.query(1, 3) << endl;
    cout << "Sum of range [0, 5]: " << st.query(0, 5) << endl;
    
    return 0;
}

2. 懒惰传播

懒惰传播用于在 O(log n) 时间复杂度内进行高效的区间更新。

带懒惰传播的线段树

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

class LazySegmentTree {
private:
    vector<long long> tree, lazy;
    int n;
    
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2*node, start, mid);
            build(arr, 2*node+1, mid+1, end);
            tree[node] = tree[2*node] + tree[2*node+1];
        }
    }
    
    void updateLazy(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void updateRange(int node, int start, int end, int l, int r, int val) {
        updateLazy(node, start, end);
        if (start > r || end < l) {
            return;
        }
        
        if (start >= l && end <= r) {
            tree[node] += val * (end - start + 1);
            if (start != end) {
                lazy[2*node] += val;
                lazy[2*node+1] += val;
            }
            return;
        }
        
        int mid = (start + end) / 2;
        updateRange(2*node, start, mid, l, r, val);
        updateRange(2*node+1, mid+1, end, l, r, val);
        updateLazy(2*node, start, mid);
        updateLazy(2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    
    long long queryRange(int node, int start, int end, int l, int r) {
        if (start > r || end < l) {
            return 0;
        }
        updateLazy(node, start, end);
        if (start >= l && end <= r) {
            return tree[node];
        }
        
        int mid = (start + end) / 2;
        long long p1 = queryRange(2*node, start, mid, l, r);
        long long p2 = queryRange(2*node+1, mid+1, end, l, r);
        return p1 + p2;
    }
    
public:
    LazySegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(arr, 1, 0, n-1);
    }
    
    void update(int l, int r, int val) {
        updateRange(1, 0, n-1, l, r, val);
    }
    
    long long query(int l, int r) {
        return queryRange(1, 0, n-1, l, r);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    LazySegmentTree lst(arr);
    
    cout << "Original array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "Sum of range [1, 3]: " << lst.query(1, 3) << endl;
    
    // Range update: add 10 to range [1, 3]
    lst.update(1, 3, 10);
    cout << "After adding 10 to range [1, 3]:" << endl;
    cout << "Sum of range [1, 3]: " << lst.query(1, 3) << endl;
    cout << "Sum of range [0, 5]: " << lst.query(0, 5) << endl;
    
    // Another range update
    lst.update(2, 4, 5);
    cout << "After adding 5 to range [2, 4]:" << endl;
    cout << "Sum of range [2, 4]: " << lst.query(2, 4) << endl;
    
    return 0;
}

3. 高级应用

高级线段树应用，包括区间最小/最大查询和坐标压缩。

区间最小查询 (RMQ) 线段树

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

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

int main() {
    vector<int> arr = {1, 3, 2, 7, 9, 11};
    RMQSegmentTree rmq(arr);
    
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "RMQ(1, 3): " << rmq.query(1, 3) << endl;
    cout << "RMQ(2, 5): " << rmq.query(2, 5) << endl;
    cout << "RMQ(0, 5): " << rmq.query(0, 5) << endl;
    
    rmq.update(2, 0);
    cout << "After updating index 2 to 0:" << endl;
    cout << "RMQ(1, 3): " << rmq.query(1, 3) << endl;
    cout << "RMQ(0, 5): " << rmq.query(0, 5) << endl;
    
    return 0;
}

总结

  • 基础线段树：在 O(log n) 时间内进行高效的区间查询和点更新
  • 懒惰传播：通过延迟计算进行区间更新优化
  • 区间最小/最大：可适应不同的结合运算
  • 应用：区间和、RMQ、坐标压缩和区间问题
  • 空间复杂度：存储树结构需要 O(4n) 空间