如何优化键值对区间查询求和算法，降低O(n²)时间复杂度？

问题描述 #

给定四个数组：keys、values、left、right。keys与values长度相同，left与right长度相同，对应查询请求。每个查询的left[i]和right[i]指定索引区间，需在该区间内为每个key选取对应最大value求和，且已处理的索引位置后续查询需忽略。

示例：当keys=[1,2,1,1,3]、values=[5,3,4,5,2]、left=[0,0]、right=[2,4]时，结果为[8,7]。

暴力解法（O(n²)） #

以下是时间复杂度为O(n²)的Java暴力实现：

public List<Integer> solve(int[] keys, int[] values, int[] left, int[] right) {
    List<Integer> result = new ArrayList<>();
    for(int i=0; i<left.length; i++) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int j=left[i]; j<=right[i]; j++) {
            int last = map.getOrDefault(keys[j], 0);
            map.put(keys[j], Math.max(last, values[j]));
            values[j] = 0; // 标记为已处理，后续查询跳过
        }
        int sum = 0;
        for(int e : map.values()) sum += e;
        result.add(sum);
    }
    return result;  
}

优化方案：离线处理+并查集（时间复杂度O((n+q)α(n))） #

暴力解法的瓶颈在于每次查询都要遍历区间内所有元素，且重复检查未被标记的位置。我们可以通过离线查询排序+并查集快速跳过已处理位置的方式，将时间复杂度降低到近乎线性。

核心思路 #

1. 离线处理查询：将所有查询按右边界从小到大排序，按顺序扩展处理区间，避免重复扫描。
2. 预处理Key的条目：为每个key收集所有对应的(index, value)对，并按value降序排序，确保优先处理每个key的最大可用value。
3. 并查集标记已处理位置：用并查集维护每个位置的"下一个未被处理的位置"，当某个位置被处理后，查询时直接跳到下一个可用位置，避免重复检查。

具体步骤 #

1. 预处理Key数据：

   • 用Map<Integer, List<Pair<Integer, Integer>>>存储每个key对应的索引和value。
   • 对每个key对应的列表按value降序排序，优先获取该key的最大value。

2. 离线排序查询：

   • 将每个查询封装为包含left、right、originalIndex的对象，按right从小到大排序。

3. 初始化并查集：

   • 构建parent数组，parent[i] = i，表示初始时每个位置都未被处理。
   • 实现带路径压缩的find函数，快速找到当前位置的第一个未被处理的节点。

4. 处理排序后的查询：

   • 遍历每个查询，对每个key的条目列表，找到第一个在[left, right]区间内且未被处理的位置。
   • 将该位置的value加入当前查询总和，通过并查集将该位置的父节点更新为index+1，标记为已处理。
   • 将总和存入结果数组的对应原始索引位置。

Java实现示例 #

import java.util.*;

public class OptimizedSolution {
    static class Query {
        int left;
        int right;
        int idx;
        Query(int l, int r, int i) {
            left = l;
            right = r;
            idx = i;
        }
    }

    private int[] parent;

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public List<Integer> solve(int[] keys, int[] values, int[] left, int[] right) {
        int n = keys.length;
        int q = left.length;
        List<Integer> result = new ArrayList<>(Collections.nCopies(q, 0));

        // 预处理每个key的(index, value)，按value降序排序
        Map<Integer, List<Pair<Integer, Integer>>> keyMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            keyMap.computeIfAbsent(keys[i], k -> new ArrayList<>())
                  .add(new Pair<>(i, values[i]));
        }
        for (List<Pair<Integer, Integer>> list : keyMap.values()) {
            list.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));
        }

        // 离线排序查询
        List<Query> queries = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            queries.add(new Query(left[i], right[i], i));
        }
        queries.sort((a, b) -> Integer.compare(a.right, b.right));

        // 初始化并查集
        parent = new int[n + 1]; // 多一个位置处理边界情况
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        // 处理每个查询
        for (Query query : queries) {
            int l = query.left;
            int r = query.right;
            int sum = 0;

            for (Map.Entry<Integer, List<Pair<Integer, Integer>>> entry : keyMap.entrySet()) {
                List<Pair<Integer, Integer>> pairs = entry.getValue();
                for (Pair<Integer, Integer> pair : pairs) {
                    int idx = pair.getKey();
                    if (idx < l || idx > r) continue;
                    int root = find(idx);
                    if (root <= r) { // 该位置未被处理
                        sum += pair.getValue();
                        parent[root] = root + 1; // 标记为已处理，跳到下一个位置
                        break; // 取到该key的最大可用值，无需继续遍历
                    }
                }
            }

            result.set(query.idx, sum);
        }

        return result;
    }

    // 自定义Pair实现
    static class Pair<K, V> {
        private K key;
        private V value;
        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }
}

复杂度分析 #

• 预处理key数据：O(n log n)，所有key的列表排序总时间为O(n log n)。
• 排序查询：O(q log q)。
• 处理查询：每个位置最多被处理一次，每次find操作时间为O(α(n))（α为阿克曼函数的反函数，近乎常数），总时间为O((n+q)α(n))。
  整体时间复杂度远低于暴力解法的O(n²)，适合处理大规模数据。

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