线段树c++模板代码

线段树（Segment Tree），也称为区间树，是一种数据结构，主要用于处理区间查询和更新的问题。在C++中，我们可以使用模板类来创建通用的线段树。下面是一个基础的二叉线段树模板代码示例：

template <typename T>
struct SegmentTree {
private:
    int n;
    std::vector<T> tree;

public:
    // 构造函数，初始化大小为n的空树
    SegmentTree(int n) : n(n), tree(2 * n) {}

    // 设置节点值
    void set(int idx, const T& val) {
        idx += n; // 树里每个元素对应的原数组索引加根节点位置n
        tree[idx] = val;
        while (idx > 0) { // 折半查找更新到根节点
            idx >>= 1;
            tree[idx] = combine(tree[idx * 2], tree[idx * 2 + 1]);
        }
    }

    // 查询区间内的元素之和
    T query(int left, int right) {
        return querySum(left, right, 0, 0, n);
    }

private:
    // 查询范围和的辅助函数
    T querySum(int L, int R, int i, int left, int right) {
        if (L >= right || left >= R)
            return 0;
        else if (L <= left && right <= R)
            return tree[i];
        else {
            int mid = (left + right) / 2;
            return combine(querySum(L, R, 2 * i, left, mid),
                           querySum(L, R, 2 * i + 1, mid + 1, right));
        }
    }

    // 合并两个节点的函数，取决于具体的实现需求，例如求和、最大值等
    T combine(T a, T b) {
        return a + b; // 这里假设我们是在做区间和的操作，如果其他操作需要替换此部分
    }
};