数据结构: 可持久化线段树(主席树)入门_可持久化线段树java版本

题目链接

问题大意

 给出n个整数,m次访问,每次访问有三个整数l, r, k
 要求输出在n个整数中, 在区间[l, r]内的升序排列情况下的第k个的数

Input Sample

5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

Output Sample

6405
15770
26287
25957
26287

分析

 这就是一道活生生的主席树模板题了, 首先介绍一下什么是主席树:
主席树是一颗线段树,每个节点记录着数组中这个落在这个区间范围的数字有多少个.

普通线段树处理

先看用普通线段树处理的情况
 例:有数据: 1, 3, 4, 2, 5
则最终的线段树为

红色数字代表数组内还有该区间数字的个数, 黑色数字代表区间.
 这样一颗线段树构建好后,我们可以轻易的找到总区间第k个数(即小于等于此数的数字有k个): 因为数据自然有序, 只需要找到个数为k时对应的数就好
 如在此树种寻找第4个, 首先判断根节点的左子树, 有3个, 少于4个, 则向右子树递归寻找第4-3=1个
 在右子树搜索时,同样按照上述原则, 右子树记录的数字为2个, 大于1, 则往递归在左子树(即代表区间[4,4]的节点搜索) 此时记录的节点刚好为1, 则我们要寻找的答案即为4.
 弄懂了这样一棵线段树后,我们就能很轻松的找到全区间的第k个树了, 那么, 我们要怎么样来找到某个区间内的第k个数呢?

从普通线段树到主席树

 一个很自然的想法就是, 每插入一个数就建立一颗新的线段树, 在访问[l, r] 区间时只需要将第r棵线段树的结果减去第l-1棵线段树的结果即可. 这确实是一个可行的想法, 但这样n个数字就需要n+1棵线段树,空间复杂度为$O(n^2)$, 复杂度爆表!!! 我们不可能采用这种方法.
 为什么会有这么高的空间复杂度呢, 因为有大量的树节点是重复的, 所以我们又有一个新的想法, 充分利用这些公用的树节点, 那么每增加一个数字只需要增加$log(n)$个节点, 则空间复杂度降低到了$O(nlog(n))$.这变得可以接受了.

具体实现及注释

 下面给出代码和注释

/*
 * Copyright (c) 2019 Ng Kimbing, HNU, All rights reserved. May not be used, modified, or copied without permission.
 * @Author: Ng Kimbing, HNU.
 * @LastModified:2019-04-11 T 14:51:19.147 +08:00
 */
package ACMProblems.DataStructureProblem.ChairmanTree;

import MyUtil.Discretization;

import java.io.*;
import java.util.Arrays;

public class TreeModel {
    static PrintWriter printWriter = new PrintWriter(new BufferedOutputStream(System.out));
    static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws Exception {
        streamTokenizer.nextToken();
        return (int) streamTokenizer.nval;
    }

    static char nextChar() throws Exception {
        streamTokenizer.nextToken();
        return streamTokenizer.sval.charAt(0);
    }

    private static final int SIZE = 100000;
    private static int nodeCount = 0;
    private static int[] a = new int[SIZE];
    private static int[] b = new int[SIZE];
    private static int[] root = new int[SIZE];
    private static int[] sum = new int[SIZE * 20];         //储存节点的id
    private static int[] leftChild = new int[SIZE * 20];   //储存节点的id
    private static int[] rightChild = new int[SIZE * 20];  //储存节点的id

    /**
     * Initialize the first empty tree. (root[0])
     *
     * @param ID the id of the root
     * @param l  left
     * @param r  right
     */
    private static void setFirstTreeID(int ID, int l, int r) {
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        leftChild[ID] = ++nodeCount;
        rightChild[ID] = ++nodeCount;
        setFirstTreeID(leftChild[ID], l, mid);
        setFirstTreeID(rightChild[ID], mid + 1, r);
    }

    /**
     * insert a the value p and create new nodes.
     *
     * @param oldNode the ID of the predecessor of the new one.
     * @param left    first index, inclusive
     * @param right   last index, exclusive.
     * @return the new node (an alternative to oldNode)
     */
    private static int getNewTree(int oldNode, int left, int right, int insertedNum) {
        int newNode = ++nodeCount;   //Create a new node.
        //update the value of the node. (Due to the insertion of a new number)
        sum[newNode] = sum[oldNode] + 1;
        //set default child.
        leftChild[newNode] = leftChild[oldNode];
        rightChild[newNode] = rightChild[oldNode];
        //if the node is a leaf.
        if (left == right)
            return newNode;
        int mid = (left + right) >> 1;
        //Determine which interval the inserted number is in.
        if (insertedNum <= mid)
            leftChild[newNode] = getNewTree(leftChild[newNode], left, mid, insertedNum);
        else
            rightChild[newNode] = getNewTree(rightChild[newNode], mid + 1, right, insertedNum);
        return newNode;
    }

    /**
     * find the kth number in an interval.
     *
     * @param oldTreeNode The previous tree corresponding to the lower bound of the interval
     * @param newTreeNode The tree corresponding to the upper bound of the interval
     * @param nodeLeft    The lower bound of current node.
     * @param nodeRight   The upper bound of the current node.
     * @param k           index.
     * @return return the index of the answer;
     */
    private static int query(int oldTreeNode, int newTreeNode, int nodeLeft, int nodeRight, int k) {
        if (nodeLeft == nodeRight)
            return nodeLeft;
        //try the whole interval
        int mid = ((nodeLeft + nodeRight) >> 1), x = sum[leftChild[newTreeNode]] - sum[leftChild[oldTreeNode]];
        //Narrow the search interval
        return x >= k ? query(leftChild[oldTreeNode], leftChild[newTreeNode], nodeLeft, mid, k) :
                query(rightChild[oldTreeNode], rightChild[newTreeNode], mid + 1, nodeRight, k - x);//pay attention to the parameter:k-x
    }

    private static int find(int left, int right, int k, int eleNum) {
        return b[query(root[left - 1], root[right], 1, eleNum, k)];
    }

    public static void main(String[] args) throws Exception {
        int k, eleNum;
        int n = nextInt();
        int m = nextInt();
        for (int i = 1; i <= n; i += 1) {
            a[i] = nextInt();
            b[i] = a[i];
        }
        Arrays.sort(b, 1, n + 1);
        eleNum = Discretization.unique(b, 1, n + 1) - 1;
        root[0] = ++nodeCount;
        setFirstTreeID(root[0], 1, eleNum);
        for (int i = 1; i <= n; ++i) {
            int indexOfInsertedNum = Discretization.lowerBound(b, 1, eleNum + 1, a[i]);
            root[i] = getNewTree(root[i - 1], 1, eleNum, indexOfInsertedNum);
        }
        while (m-- != 0) {
            int left, right;
            left = nextInt();
            right = nextInt();
            k = nextInt();
            printWriter.println(find(left, right, k, eleNum));
        }
        printWriter.flush();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129