老管家的忠诚2（线段树）

解题思路: 代码分为线段树构建（build_tree）、区间查询（query）、单点更新（update）和主函数（main）四部分
注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

// 线段树空间大小：根据线段树特性，需为原始数组的4倍以上以避免越界
const int N = 4e5 + 10;

int t[N];       // 线段树数组，每个节点存储对应区间的最小值
int a[N];       // 原始数据数组
int n, m;       // n：原始数组长度；m：操作次数
int p, x, y;    // p：操作类型（1表示查询，其他表示更新）；x,y：操作参数

/**
 * 构建线段树
 * @param pt 当前节点编号（根节点为1，左孩子为2*pt，右孩子为2*pt+1）
 * @param l 当前节点负责的区间左端点
 * @param r 当前节点负责的区间右端点
 * @return 当前节点区间的最小值（供父节点计算）
 */
int build_tree(int pt, int l, int r){
    // 叶子节点：区间长度为1，直接存储原始数组的值
    if(l == r){
        t[pt] = a[l];
        return a[l];
    }
    // 非叶子节点：分裂为左右子树并递归构建
    int mid = (l + r) / 2;                  // 计算区间中点，分割左右子树
    int lm = build_tree(2 * pt, l, mid);    // 构建左子树，返回左区间最小值
    int rm = build_tree(2 * pt + 1, mid + 1, r);  // 构建右子树，返回右区间最小值
    t[pt] = min(lm, rm);                    // 当前节点值为左右子树最小值的较小者
    return t[pt];                           // 返回当前节点值，供父节点计算
}

/**
 * 区间最小值查询
 * @param pt 当前节点编号
 * @param start 当前节点负责的区间左端点
 * @param end 当前节点负责的区间右端点
 * @param l 目标查询区间的左端点
 * @param r 目标查询区间的右端点
 * @return 目标区间[l, r]的最小值
 */
int query(int pt, int start, int end, int l, int r){
    // 情况1：当前节点区间与查询区间完全不重叠，返回极大值（不影响最小值计算）
    if(l > end || r < start) return 0x3f3f3f3f;
    // 情况2：当前节点区间完全被查询区间包含，直接返回当前节点的值
    if(l <= start && r >= end)
        return t[pt];
    // 情况3：部分重叠，递归查询左右子树
    int mid = (start + end) / 2;                        // 基于当前节点区间计算中点
    int left_min = query(2 * pt, start, mid, l, r);     // 查询左子树区间
    int right_min = query(2 * pt + 1, mid + 1, end, l, r);  // 查询右子树区间
    return min(left_min, right_min);                    // 返回左右子树结果的最小值
}

/**
 * 单点更新：将原始数组x位置的值改为y，并同步更新线段树
 * @param x 要更新的位置（原始数组下标）
 * @param y 新值
 */
void update(int x, int y){
    a[x] = y;                 // 先更新原始数组
    int pt = 1;               // 从根节点开始查找目标叶子节点
    int s = 1, e = n;         // 当前节点覆盖的区间（初始为根节点的[1, n]）
    
    // 步骤1：定位到x对应的叶子节点
    while(s != e){
        int mid = (s + e) / 2;
        if(x <= mid){         // x在左子树区间内
            pt = 2 * pt;      // 移动到左孩子节点
            e = mid;          // 更新当前区间为左子树区间[start, mid]
        } else {              // x在右子树区间内
            pt = 2 * pt + 1;  // 移动到右孩子节点
            s = mid + 1;      // 更新当前区间为右子树区间[mid+1, end]
        }
    }
    t[pt] = y;                // 更新叶子节点的值
    
    // 步骤2：向上更新所有祖先节点（从父节点到根节点）
    while(pt > 1){
        pt /= 2;              // 移动到父节点
        t[pt] = min(t[2 * pt], t[2 * pt + 1]);  // 父节点值为左右孩子的最小值
    }
}

int main(){
    cin >> n >> m;                    // 输入数组长度n和操作次数m
    for(int i = 1; i <= n ; ++ i)     // 输入原始数组元素
        scanf("%d", &a[i]);
    build_tree(1, 1, n);              // 构建线段树（根节点编号1，覆盖区间[1, n]）
    
    // 处理m次操作
    while(m --){
        scanf("%d %d %d", &p, &x, &y);  // 读取操作类型和参数（优化为scanf提高效率）
        if(p == 1){
            // 操作1：查询[x, y]区间的最小值
            int ans = query(1, 1, n, x, y);  // 从根节点开始查询
            printf("%d ", ans);
        } else {
            // 其他操作：将位置x的值更新为y
            update(x, y);
        }
    }
    return 0;
}