TreeMap是一个有序的HashMap映射(不是hash实现),基于红黑树实现,增删改查均为O(log(n))
步骤
1. 首先将插入点和查询点加入TreeMap
2. 插入完成之后,将map中每个key的排序序号从1开始,设置到key对应的值中
3. 此时进行插入,从map中查出插入值的序号,在数组对应序号的位置加上对应值(数组可以预先建立足够大,也可以根据 刚才序号最大值建立)
4. 建立前缀和,根据查询从前缀和中查询
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int N = 300010;
int arr[][] = new int[n][2];
int brr[][] = new int[m][2];
for (int i = 0; i < arr.length; i++) {
arr[i][0] = scanner.nextInt();
arr[i][1] = scanner.nextInt();
}
for (int i = 0; i < brr.length; i++) {
brr[i][0] = scanner.nextInt();
brr[i][1] = scanner.nextInt();
}
int nums[] = new int[N];
int pre[] = new int[N];
// 1.此时插入TreeMap
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] ints : arr) {
int num = ints[0];
map.put(num, 0);
}
for (int[] ints : brr) {
map.put(ints[0], 0);
map.put(ints[1], 0);
}
// 2.刷新值
Set<Integer> set = map.keySet();
int index = 1;
for (Integer integer : set) {
map.put(integer, index++);
}
// 3.插入值
for (int[] ints : arr) {
nums[map.get(ints[0])] += ints[1];
}
// 4.前缀和,并且查询
for (int i = 1; i < index; i++) {
pre[i] = nums[i] + pre[i - 1];
}
for (int[] ints : brr) {
int l = ints[0];
int r = ints[1];
System.out.println(pre[map.get(r)] - pre[map.get(l) - 1]);
}
}
}