题目地址

区间和

问题

求区间和可以用前缀和，但坐标范围太大了，无法创建这么大的数组（会有很多用不到的无效空间）。

解决方法

将所有坐标映射为从0开始的自然数。

思路

将所有可能用到的坐标进行排序、去重得到一个映射数组。数组中的值保存的是坐标的值。利用二分查找可以快速找到坐标对应的数组下标。

实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Main {
    private static int find(List<Integer> list, int x){
        int l = 0, r = list.size() - 1;

        while(l < r){
            int mid = l + r + 1 >> 1;
            if(list.get(mid) <= x){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        return l + 1;
    }

    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));
        int n, m;
        Integer[] temp = Stream.of(br.readLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
        n = temp[0];
        m = temp[1];
        ArrayList<Integer[]> op = new ArrayList<Integer[]>();
        ArrayList<Integer[]> query = new ArrayList<Integer[]>();
        List<Integer> idx = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) {
            Integer[] array = Stream.of(br.readLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
            op.add(array);
            idx.add(array[0]);
        }
        for (int i = 0; i < m; i++) {
            Integer[] array = Stream.of(br.readLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
            query.add(array);
            idx.add(array[0]);
            idx.add(array[1]);
        }
        Collections.sort(idx);
        int[] v = new int[idx.size() + 1];
        idx = idx.stream().distinct().collect(Collectors.toList());
        for (Integer[] arr : op) {
            int i = find(idx, arr[0]);
            v[i] += arr[1];
        }
        for (int i = 1; i < v.length; i++) {
            v[i] = v[i] + v[i - 1];
        }
        for (Integer[] arr : query) {
            int l = 0, r = 0;
            try {
                l = find(idx, arr[0]);;
                r = find(idx, arr[1]);;
            } catch (Exception e) {
                System.out.println(l + " " + r);
            }
            int res = 0;
            res = v[r] - v[l - 1];
            System.out.println(res);
        }

    }
}