线段树

发表于 | 分类于 | 阅读次数：

线段树

动态求数组的区间和

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

/**
 * 线段树
 * arr[] = {1, 3, 5, 7, 9, 11}
 * tree[] = {36,9,27,4,5,16,11,1,3,0,0,7,9,0,0}
 *                   36 [0-5]
 *    [0-2]  9                  27[3-5]
 * [0-1] 4      5[2]       16[3-4]    11[5]
 *   1     3             7    9
 *  [0]    [1]          [3]   [4]
 */
public class segmentTree {

    private static void buildTree(int[] arr, int[] tree, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int leftNode = 2 * node + 1;
            int rightNode = 2 * node + 2;

            int mid = start + (end - start) / 2;
            buildTree(arr, tree, leftNode, start, mid);
            buildTree(arr, tree, rightNode, mid + 1, end);
            tree[node] = tree[leftNode] + tree[rightNode];
        }
    }

    // 将arr[]的idx下标改成val值
    private static void update(int[] arr, int[] tree, int node, int start, int end, int idx, int val) {
        if (start == end) {
            arr[idx] = val;
            tree[node] = val;
        } else {
            int leftNode = 2 * node + 1;
            int rightNode = 2 * node + 2;
            int mid = start + (end - start) / 2;
            if (idx >= start && idx <= mid) {
                update(arr, tree, leftNode, start, mid, idx, val);
            } else {
                update(arr, tree, rightNode, mid + 1, end, idx, val);
            }
            tree[node] = tree[leftNode] + tree[rightNode];
        }
    }

    // 求arr数组中下标left到right的和
    private static int query(int[] arr, int[] tree, int node, int start, int end, int left, int right) {
        if (left > end || right < start) {
            return 0;
        } else if (start >= left && end <= right) {
            return tree[node];
        } else if (left == right) {
            return tree[node];
        }
        int leftNode = 2 * node + 1;
        int rightNode = 2 * node + 2;
        int mid = start + (end - start) / 2;
        int leftSum = query(arr, tree, leftNode, start, mid, left, right);
        int rightSum = query(arr, tree, rightNode, mid + 1, end, left, right);
        return leftSum + rightSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int[] tree = new int[1000];
        buildTree(arr, tree, 0, 0, arr.length - 1);
        for (int i = 0; i < 15; i++) {
            System.out.print(tree[i] + "  ");
        }
        System.out.println();

        int sum1 = query(arr, tree, 0, 0, arr.length - 1, 2, 5);
        System.out.println(sum1);

        update(arr, tree, 0, 0, arr.length - 1, 4, 6);
        for (int i = 0; i < 15; i++) {
            System.out.print(tree[i] + "  ");
        }
        System.out.println();
        int sum2 = query(arr, tree, 0, 0, arr.length - 1, 2, 5);
        System.out.println(sum2);
    }
}