用于查找两高度间行范围的高效数据结构选型问询

这个问题本质是要解决动态前缀和的快速查询与更新——你要找的行范围，其实就是定位前缀和落在[start_height, end_height)区间对应的行索引（根据你的例子，可能需要微调边界判断）。朴素遍历的查询复杂度是O(n)，在数据量大的时候肯定不够用，下面给你几个能把插入、删除、查询都优化到O(logn)级别（或接近）的解决方案：

1. 线段树（Segment Tree） #

这是最适配你场景的选择，既能高效维护区间和，又能快速定位目标前缀和的位置。

核心逻辑 #

线段树的每个节点存储对应区间内lineHeights的总和。查询时，我们可以像二分查找一样遍历树：

• 如果左子树的总和小于目标高度，就减去左子树的和，递归查询右子树；
• 如果左子树总和≥目标高度，就递归查询左子树；
• 直到走到叶子节点，就能找到对应的行索引。

插入或删除操作时，只需要更新对应位置的叶子节点，再向上回溯更新所有父节点的总和即可，全程O(logn)。

实现思路（伪代码） #

// 线段树节点结构
struct SegmentTreeNode {
    int start, end;
    long long sum; // 用long long避免溢出
    SegmentTreeNode *left, *right;
    SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};

// 构建线段树
SegmentTreeNode* build(vector<int>& lines, int start, int end) {
    SegmentTreeNode* node = new SegmentTreeNode(start, end);
    if (start == end) {
        node->sum = lines[start];
        return node;
    }
    int mid = (start + end) / 2;
    node->left = build(lines, start, mid);
    node->right = build(lines, mid+1, end);
    node->sum = node->left->sum + node->right->sum;
    return node;
}

// 找到第一个前缀和 >= target 的行索引（前缀和从第0行到当前行的总和）
int find_index(SegmentTreeNode* root, long long target, long long current_sum = 0) {
    if (root->start == root->end) {
        return root->start;
    }
    long long left_total = current_sum + root->left->sum;
    if (left_total >= target) {
        return find_index(root->left, target, current_sum);
    } else {
        return find_index(root->right, target, left_total);
    }
}

// 更新某个位置的行高（插入/删除可通过扩展线段树或调整值实现）
void update(SegmentTreeNode* root, int idx, int new_val) {
    if (root->start == root->end) {
        root->sum = new_val;
        return;
    }
    if (idx <= root->left->end) {
        update(root->left, idx, new_val);
    } else {
        update(root->right, idx, new_val);
    }
    root->sum = root->left->sum + root->right->sum;
}

// 获取目标行范围
vector<int> get_line_range_between_heights(SegmentTreeNode* root, long long start_h, long long end_h) {
    int start_idx = find_index(root, start_h);
    // 注意：这里的边界要根据你的需求调整，比如你的例子中是找行高本身在区间内，可能需要额外判断
    // 如果你是找前缀和覆盖[start_h, end_h)的行，那么end_idx是find_index(root, end_h) - 1
    int end_idx = find_index(root, end_h) - 1;
    return {start_idx, end_idx};
}

2. 树状数组（Fenwick Tree）+ 二分查找 #

如果想追求更简单的实现，树状数组是个不错的选择——它天生擅长维护前缀和的单点更新与查询，但要定位目标前缀和的位置，需要结合二分查找，整体查询复杂度是O(log²n)，比线段树略高，但代码量小很多。

核心逻辑 #

• 用树状数组维护前缀和，单点更新（插入/删除）是O(logn)；
• 查询时，二分遍历行索引范围，每次用树状数组查当前mid的前缀和，和目标高度比较，逐步缩小范围，找到第一个前缀和≥target的索引，这个过程是O(logn)的二分 × O(logn)的前缀和查询，即O(log²n)。

注意 #

树状数组更适合插入删除在末尾的场景，如果需要在任意位置插入删除，需要额外维护一个动态索引映射（比如用平衡树），复杂度会上升，这时候不如用线段树。

3. 带左子树总和的平衡二叉搜索树 #

如果你熟悉平衡树的实现（比如Treap、Splay Tree），可以给每个节点增加一个left_sum字段，存储左子树所有行高的总和。这样查询时，就能通过累加left_sum快速定位目标前缀和的位置，插入删除也能在O(logn)时间内维护left_sum。

核心逻辑 #

• 每个节点存储行高val、左子树总和left_sum、左子树节点数size；
• 查询目标高度时，遍历树的过程中判断左子树总和是否能覆盖剩余目标值，决定走左或右子树；
• 插入删除时，同步更新路径上所有节点的left_sum。

这种方案的优势是在某些场景下（比如频繁的范围查询）可能更灵活，但实现复杂度比线段树高。

方案对比 #

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