[数据结构与算法]离散化 java实现

一.什么是离散化

来自百度百科：
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

举个例子：在一个数轴上，有串数字：

我们需要得出此数轴的数字的相对位置，我们可以看出数轴的范围/空间（index）非常的大，但是其中有值的个数非常的少，只有6个，而且它们分布非常不均匀，我们总不能开个10^9的数组来存，此时就可以进行离散化处理，变成：

离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

二.例题

区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

?10^9≤x≤10^9,
1≤n,m≤10^5,
?10^9≤l≤r≤10^9,
?10000≤c≤10000

输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例：
8
0
5

可以发现此题的数据范围非常大（?10^ 9 ≤x≤10^ 9)，而有值的则非常少（1≤n,m≤10^5），因此我们可以通过离散化+前缀和来实现。

解法一

普通解法

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    static int[] a,s;//a是离散化处理后的数组，s是其前缀和数组
    static final int N = 300010;//数组范围nm都是10^5，而m又有两个数字（区间），所以离散化后的a数组最多有3*10^5个值
    static int n, m;
    static List<Integer> alls, dtAlls;//alls:存放所有要操作的数（下标） dtAlls:存储alls排序和去重后的
    static ArrayList<Pair> add, query;//add:存放要添加的位置和值  query:存要查询的区间

    public static void main(String[] args) throws IOException {

        //读入数据并且存入到相应的数据结构
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.nextToken();
        n = (int) st.nval;
        st.nextToken();
        m = (int) st.nval;
        a = new int[N];
        s = new int[N];
        alls = new ArrayList<>();
        add = new ArrayList<>();
        query = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            st.nextToken();
            int x = (int) st.nval;
            st.nextToken();
            int c = (int) st.nval;
            add.add(new Pair(x, c));
            alls.add(x);
        }
        for (int i = 1; i <= m; i++) {
            st.nextToken();
            int l = (int) st.nval;
            st.nextToken();
            int r = (int) st.nval;
            query.add(new Pair(l, r));
            alls.add(l);
            alls.add(r);
        }

        //离散化
        Collections.sort(alls);//对存放的所有要操作的数（下标）进行排序
        dtAlls = alls.stream().distinct().collect(Collectors.toList());//去重

        //处理插入
        for (Pair item : add) {
            int x = find(item.first);//二分找到x离散化后的位置（下标）
            a[x] += item.second;//x+c
        }

        //预处理前缀和 这里的长度是dtAlls（因为find返回的是r+1，所以下标从1开始，要<=dtAlls.size()保证数据个数不变）
        for (int i = 1; i <= dtAlls.size(); i++) {
            s[i] = a[i] + s[i - 1];
        }

        //处理询问
        for (int i = 0; i < query.size(); i++) {
            int l = find(query.get(i).first);
            int r = find(query.get(i).second);
            pw.println(s[r] - s[l - 1]);
            pw.flush();
        }
    }

    //找到x离散化后的位置（下标）
    static int find(int x) {
        int l = 0, r = dtAlls.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(dtAlls.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return r + 1;//这里+1是因为后面有前缀和的计算，方便处理边界问题
    }
}

class Pair {
    int first, second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

解法二

（来自：AcWing 802. 区间和_java_35行）
这里借助TreeMap来实现
TreeMap：底层是红黑树实现的。可以简单理解为有序的HashMap。
getOrDefault(key, default): 获取key对应的value，如果没有key，则返回默认值default。
ceilingEntry(key): 返回大于等于key的Entry（二分）
lowerEntry(key)： 返回小于key的Entry（二分），注意，如果没有key，会报空指针异常。

import java.io.*;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.nextToken();
        int n = (int) st.nval;
        st.nextToken();
        int m = (int) st.nval;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();//会自动根据key排序
        for (int i = 1; i <= n; i++) {//对有值的数进行离散化
            st.nextToken();
            int x = (int) st.nval;
            st.nextToken();
            int c = (int) st.nval;
            treeMap.put(x, treeMap.getOrDefault(x, 0) + c);
        }
        int[][] query = new int[m + 1][2];//查询区间数组
        for (int i = 1; i <= m; i++) {//对要查询的数进行离散化
            st.nextToken();
            query[i][0] = (int) st.nval;//l
            st.nextToken();
            query[i][1] = (int) st.nval;//r
            treeMap.put(query[i][0], treeMap.getOrDefault(query[i][0], 0));
            treeMap.put(query[i][1], treeMap.getOrDefault(query[i][1], 0));
        }
        Object[] keys = treeMap.keySet().toArray();//将下标（key）转换为数组
        //求前缀和
        for (int i = 1; i < keys.length; i++) {
            treeMap.put((Integer) keys[i], treeMap.get(keys[i - 1]) + treeMap.get(keys[i]));
        }
        //通过前缀和求区间和
        for (int i = 1; i <= m; i++) {
            if (query[i][0] == (Integer) keys[0])//是第一个下标，直接求即可，不用减l-1
                pw.println(treeMap.get(query[i][1]));
            else
                pw.println(treeMap.get(query[i][1]) - treeMap.lowerEntry(query[i][0]).getValue());
            pw.flush();
        }
    }
}