线段树

一. 概述

线段树（Segment Tree）是一种用于处理区间查询和更新的数据结构
常用于解决一维区间相关的问题，如区间最值、区间和、区间乘积等

线段树的基本思想是将区间划分为一些小的子区间，并在每个子区间上维护一些信息
例如该区间的最值、和、乘积等，通过将大区间不断划分为小区间，直到每个小区间只包含一个元素
从而建立一棵二叉树的结构，这棵树就是线段树

二. 构建方式

1. 将待处理的区间划分为两半，分别对左半部分和右半部分递归地构建线段树。
2. 对于每个非叶子节点，根据其左子节点和右子节点的信息，更新该节点的信息，例如可以计算最值、和、乘积等。
3. 当递归到叶子节点时，将叶子节点的信息设置为输入数组中对应位置的元素

构建模板

// 线段树节点结构体
struct TreeNode {
    int left; // 节点区间左边界
    int right; // 节点区间右边界
    int value; // 节点存储的信息，这里以区间最值为例
};
//建树
void build(vector<int>& arr, vector<TreeNode>& tree, int index, int left, int right)
//更新
void update(vector<TreeNode>& tree, int index, int pos, int value)
//查询
int query(vector<TreeNode>& tree, int index, int left, int right)

常用C++做题模板

// 构建线段树的函数，做题arr和tree可用全局变量，不用传入函数
void build(vector<int>& arr, vector<TreeNode>& tree, int index, int left, int right) {
    tree[index].left = left;
    tree[index].right = right;
    // 叶子节点，存储输入数组的元素值
    if (left == right) {
        tree[index].value = arr[left];
        return;
    } 
        // 非叶子节点，递归构建左子树和右子树
        int mid = (left + right) / 2;
        build(arr, tree, index * 2 + 1, left, mid);//递归建左树
        build(arr, tree, index * 2 + 2, mid + 1, right);//递归建右树
        // 更新当前节点的信息，这里以区间最值为例
        tree[index].value = min(tree[index * 2 + 1].value, tree[index * 2 + 2].value);
}

int query(vector<TreeNode>& tree, int index, int left, int right) {
    // 当前节点区间与查询区间完全重合，直接返回节点存储的信息
    if (tree[index].left == left && tree[index].right == right) 
        return tree[index].value;
    else {
        // 否则，根据查询区间与节点区间的关系递归查询左子树或右子树
        int mid = (tree[index].left + tree[index].right) / 2;
        // 查询区间完全位于左子树
        if (right <= mid) 
            return query(tree, index * 2 + 1, left, right);
        // 查询区间完全位于右子树
        else if (left > mid) 
            return query(tree, index * 2 + 2, left, right);
        // 查询区间同时位于左子树和右子树，取两者查询结果的最值
        else 
            return min(query(tree, index * 2 + 1, left, mid), query(tree, index * 2 + 2, mid + 1, right));
    }
}

// 区间更新的函数
void update(vector<TreeNode>& tree, int index, int pos, int value) {
    if (tree[index].left == tree[index].right) {
        // 叶子节点，更新节点存储的信息
        tree[index].value = value;
    } else {
        // 非叶子节点，根据更新位置与节点区间的关系递归更新左子树或右子树
        int mid = (tree[index].left + tree[index].right) / 2;
        if (pos <= mid)// 更新位置位于左子树
        update(tree, index * 2 + 1, pos, value);
         else // 更新位置位于右子树
        update(tree, index * 2 + 2, pos, value);
        // 更新当前节点的信息，这里以区间最值为例
        tree[index].value = min(tree[index * 2 + 1].value, tree[index * 2 + 2].value);
      }
}

三. 实例

1. 子数组中占绝大多数的元素