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

public class SegmentTree<E> {

private Merger<E> merger;

/**
     * 树结构 - 这里使用数组
     */
    private E[] tree;
    /**
     * 真正的数据
     */
    private E[] data;

public SegmentTree(E[] arr, Merger<E> merger) {
        this.data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

// 通过归纳，4倍的data长度用来创建线段树比较合适，可能会有空间的浪费，但是可以接受
        tree = (E[]) new Object[4 * arr.length];
        this.merger = merger;

// 创建线段树
        buildSegmentTree(0, 0, arr.length - 1);
    }

private void buildSegmentTree(int treeIndex, int l, int r) {
        ...
        ...
    }

/**
     * 获取数据大小
     *
     * @return 数据大小
     */
    public int getSize() {
        return data.length;
    }

/**
     * 根据索引获得数据
     *
     * @param index 索引值
     * @return 数据
     */
    public E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return data[index];
    }

/**
     * 返回一个索引表示的元素的左孩子的索引
     *
     * @param index 索引值
     * @return 左孩子的索引
     */
    public int leftChild(int index) {
        return 2 * index + 1;
    }

/**
     * 返回一个索引表示的元素的右孩子的索引
     *
     * @param index 索引值
     * @return 右孩子的索引
     */
    public int rightChild(int index) {
        return 2 * index + 2;
    }

@Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("[");
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null) {
                res.append(tree[i]);
            } else {
                res.append("null");
            }

if (i != tree.length - 1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
     * 在 treeIndex 的位置创建表示区间[l...r]的线段树
     *
     * @param treeIndex 正在创建的线段树的根节点
     * @param l         表示区间的左边界
     * @param r         表示区间的右边界
     */
    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }

int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

int mid = l + (r - l) / 2;
        buildSegmentTree(leftTreeIndex, l, mid);
        buildSegmentTree(rightTreeIndex, mid + 1, r);

tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }