C++实现线段树范围查询：如何返回最小值的索引？

当然可以修改，核心是让线段树每个节点同时存储区间最小值和该最小值对应的原数组索引，然后调整更新和查询逻辑来维护这个信息。以下是具体修改步骤和代码：

1. 修改线段树存储结构 #

把原来的int tree[1000000];改成存储值和索引的pair<int, int>数组，其中pair.first是区间最小值，pair.second是该值对应的原数组索引。

2. 修正原代码笔误 #

原update函数最后一行的tree[c]是笔误，应改为tree[position]；query函数的参数c建议统一改为position，和update保持一致，避免变量名混淆。

3. 调整update函数逻辑 #

叶子节点直接存储当前位置的值和原数组索引；非叶子节点比较左右子树的最小值，选择更小的那个（若值相等，优先保留索引更小的），更新当前节点的信息。

4. 重构query函数 #

将返回类型改为pair<int, int>，递归查询左右子树后，比较两个结果的最小值，返回对应的（值，索引）对。

完整修改后的代码 #

#include <algorithm>
using namespace std;

int length; // 原数组的长度
pair<int, int> tree[1000000]; // 每个节点存储(区间最小值, 对应原数组索引)

// 更新函数：修改原数组index位置的值为value
void update(int index, int value, int position = 1, int currentL = 0, int currentR = length-1) {
    if (currentL == currentR) {
        tree[position] = {value, index}; // 叶子节点直接存值和原索引
        return;
    }
    int mid = (currentL + currentR) / 2;
    if (index <= mid) {
        update(index, value, position*2, currentL, mid);
    } else {
        update(index, value, position*2+1, mid+1, currentR);
    }
    // 比较左右子树，选择最小值对应的节点（值相等时选索引更小的）
    if (tree[position*2].first < tree[position*2+1].first) {
        tree[position] = tree[position*2];
    } else if (tree[position*2].first > tree[position*2+1].first) {
        tree[position] = tree[position*2+1];
    } else {
        tree[position] = tree[position*2].second < tree[position*2+1].second ? tree[position*2] : tree[position*2+1];
    }
}

// 查询函数：返回[qL, qR]区间内的(最小值, 对应原数组索引)
pair<int, int> query(int qL, int qR, int position = 1, int cL = 0, int cR = length-1) {
    if (qL <= cL && cR <= qR) {
        return tree[position];
    }
    int mid = (cL + cR) / 2;
    // 初始化结果为极大值和无效索引
    pair<int, int> ans = {10005, -1};
    if (qL <= mid) {
        pair<int, int> leftRes = query(qL, qR, 2*position, cL, mid);
        // 比较并更新当前最优结果
        if (leftRes.first < ans.first || (leftRes.first == ans.first && leftRes.second < ans.second)) {
            ans = leftRes;
        }
    }
    if (qR > mid) {
        pair<int, int> rightRes = query(qL, qR, 2*position+1, mid+1, cR);
        // 比较并更新当前最优结果
        if (rightRes.first < ans.first || (rightRes.first == ans.first && rightRes.second < ans.second)) {
            ans = rightRes;
        }
    }
    return ans;
}

使用说明 #

调用query(qL, qR)后，返回的pair对象中：

• ans.first是查询区间内的最小值
• ans.second是该最小值在原数组中的索引（若存在多个相同最小值，默认返回索引最小的，可根据需求调整判断逻辑）

内容的提问来源于stack exchange，提问作者Redz