题目描述

给定一个1e-9到1e9长的数轴，然后任意给数轴上的点添加数字，然后求某个区间的和。

样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

算法1

(离散化) $O(nlog(n))$

思想：就是把哪个加了数值的点排序，然后映射到从1开始的下标，然后通过前缀和的形式求区间和

如何映射那？
1.自定义一个接受左右端点的类，然后放数据分别放到add和query的list的集合中 
2.把所有操作的点存到一个List中，然后对这个List,进行排序，然后去重，此时List中值是所有点并不是1，2，3
但是List是有序的，这些点的下标是从0开始的，所有可以通过二分查找找到这些点的下标
3.定义个放对应点的值的数组（a[]），通过二分查找这些点的下标，然后把点所对应的值加上去
4.对a求前缀和即可

时间复杂度 $O(nlog(n))$

参考文献：y总

Java 代码

package com.neuedu.main;

import java.util.*;

public class Test_11 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); int m = scan.nextInt();
        int[] a = new int[300010];// 存储 有序下标对应的值
        int[] s = new int[300010];// 存储 a的前缀和
        List<Integer> alls = new ArrayList<>();// 存储所有的区间数字
        List<Pairs> add = new ArrayList<>();// 存储所有添加的数据
        List<Pairs> query = new ArrayList<>();// 存储所有的查询区间
        // 一、接收数据
        for (int i = 0; i < n; i++){// 执行n次
            int x = scan.nextInt();
            int c = scan.nextInt();
            add.add(new Pairs(x, c));// 存储准备添加的下标和数值
            alls.add(x);// 存储添加的下标
        }
        for (int i = 0; i < m; i++){// 执行m次
            int l = scan.nextInt();
            int r = scan.nextInt();
            query.add(new Pairs(l, r));// 存储所有区间的左右端点
            alls.add(l);// 存储区间左端点
            alls.add(r);// 存储区间右端点
        }

        // 二、对所有存储的区间（alls）下标排序去重
        Collections.sort(alls);// 排序  nlogn次
        int j = unique(alls);// 把不重复的值放到前面并且把最后一个不重复的下标+1返回  n次
        alls = alls.subList(0, j);// 去重  1次

        // 三、找下标+值
        for (Pairs item : add){// n次
            int x = find(item.first, alls);
            a[x] += item.sesond;
        }
        // 四、求前缀和
        for (int i = 1; i <= alls.size(); i++){// n次
            s[i] = s[i - 1] + a[i];
        }
        // 五、找下表求前缀和
        for (Pairs item : query){// m次
            int l = find(item.first, alls);
            int r = find(item.sesond, alls);
            System.out.println(s[r] - s[l - 1]);
        }
        // 2m + 4n + 1 + nlogn ==> nlogn
    }
    static class Pairs{
        public int first;
        public int sesond;
        public Pairs(int first, int second){
            this.first = first;
            this.sesond = second;
        }
    }
    // 去重并返回最后一个不重复的下标+1 双指针算法
    public static int unique(List<Integer> alls){
        int j = 0;// 从0开始存放不重复的值
        for (int i = 0; i < alls.size(); i++){
            // 只要满足不是第一个 并且前一个不等于当前值 就是不重复的
            if (i == 0 || alls.get(i -1) != alls.get(i)){
                alls.set(j, alls.get(i));
                j++;
            }
        }
        return j;
    }
    // 寻找下标 从1开始 利用二分查找
    public static int find(int x, List<Integer> alls){
        int l = 0;
        int r = alls.size() - 1;
        while (l < r){
            int mid = (l + r) >> 1;
            if (alls.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return l + 1;
    }
}