七秒记忆
0%

线段树

发表于 分类于

线段树（Segment Tree） ,个人还是喜欢叫 Index Tree ，是一个满二叉树。能在 O(logN) 的时间内完成更新、查找数据。

初始化

如果当前有7个节点， 小于 8（2 的 3 次方），那么需要开辟一个（2 的 4 次方）16 大小的数组，其中前 8 个用来存父节点， 后8个存本身作为叶子节点。

具体代码实现：

1
2
3
4
5
6
7
8
9
private static void initTree() {
    int n = 0;
    while ((1 << n) < N) n++;
    maxTree = new int[1 << (n + 1)];
    minTree = new int[1 << (n + 1)];
    Arrays.fill(minTree, Integer.MAX_VALUE);

    offset = 1 << n;
}

这里初始化了两个树，一个最大值树，一个最小值树，所以使用目的不同，代码则略微有所不同。

更新

1
2
3
4
5
6
7
8
9
private static void update(int index, int value) {
    index = offset + index;
    while (index > 0) {
        maxTree[index] = Math.max(value, maxTree[index]);
        minTree[index] = Math.min(value, minTree[index]);

        index >>= 1;
    }
}

寻找区间内的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int getMax(int start, int end) {
    int max = 0;
    start = offset + start - 1;
    end = offset + end - 1;
    while (start <= end) {
        if ((start & 1) == 1) {
            max = Math.max(max, maxTree[start]);
        }
        if ((end & 1) == 0) {
            max = Math.max(max, maxTree[end]);
        }
        start = (start + 1) >> 1;
        end = (end - 1) >> 1;
    }
    return max;
}

寻找区间内的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int getMin(int start, int end) {
    start = offset + start - 1;
    end = offset + end - 1;
    int min = Integer.MAX_VALUE;
    while (start <= end) {
        if ((start & 1) == 1) {
            min = Math.min(min, minTree[start]);
        }
        if ((end & 1) == 0) {
            min = Math.min(min, minTree[end]);
        }
        start = (start + 1) >> 1;
        end = (end - 1) >> 1;
    }
    return min;
}

测试完整代码

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
public class IndexTree {
    static int N, offset;
    static int[] maxTree, minTree;

    public static void main(String[] args) {
        int[] nums = {1, 7, 2, 5, 3, 6};
        N = nums.length;
        initTree();
        for (int i = 0; i < N; i++) {
            update(i, nums[i]);
        }
        System.out.println(getMax(2, 4));
        System.out.println(getMin(2, 4));
    }

    /**
     * 初始化
     */
    private static void initTree() {
        int n = 0;
        while ((1 << n) < N) n++;
        maxTree = new int[1 << (n + 1)];
        minTree = new int[1 << (n + 1)];
        Arrays.fill(minTree, Integer.MAX_VALUE);

        offset = 1 << n;
    }

    /**
     * 更新
     */
    private static void update(int index, int value) {
        index = offset + index;
        while (index > 0) {
            maxTree[index] = Math.max(value, maxTree[index]);
            minTree[index] = Math.min(value, minTree[index]);

            index >>= 1;
        }
    }

    /**
     * 寻找区间内的最大值
     *
     * @param start
     * @param end
     * @return
     */
    private static int getMax(int start, int end) {
        int max = 0;
        start = offset + start - 1;
        end = offset + end - 1;
        while (start <= end) {
            if ((start & 1) == 1) {
                max = Math.max(max, maxTree[start]);
            }
            if ((end & 1) == 0) {
                max = Math.max(max, maxTree[end]);
            }
            start = (start + 1) >> 1;
            end = (end - 1) >> 1;
        }
        return max;
    }

    /**
     * 寻找区间内的最小值
     *
     * @param start
     * @param end
     * @return
     */
    private static int getMin(int start, int end) {
        start = offset + start - 1;
        end = offset + end - 1;
        int min = Integer.MAX_VALUE;
        while (start <= end) {
            if ((start & 1) == 1) {
                min = Math.min(min, minTree[start]);
            }
            if ((end & 1) == 0) {
                min = Math.min(min, minTree[end]);
            }
            start = (start + 1) >> 1;
            end = (end - 1) >> 1;
        }
        return min;
    }
}

推荐题目

poj2387