Garden of Sinners
0%

SegmentTree

Posted on Edited on In

记录一下【线段树】的个人模版。

记录一些好用的线段树的模版。线段树不仅能处理区域和还能处理区域积、区域最大值、区域最小值等一切可以用分治法计算的问题。
相较于树状数组更据灵活性，因为树状数组只能处理区域和（通过前缀和解决）。而同时线段树的所要求的时间复杂度也更大，树状数组是O(n)，线段树是最小O(2n)，一般为了方便找到子节点用O(4n)。

模版

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
/**
 * sum segment tree
 */
public class SegmentTree {
    
    private int[] t;
    private int n;

    public SegmentTree(int[] a) {
        n = a.length;
        t = new int[4*n];
        build(a, 1, 0, n-1);
    }

    public void update(int pos, int newVal) {
        update(1, 0, n-1, pos, newVal);
    }

    public int rangeSum(int l, int r) { // [l, r]
        return querySum(1, 0, n-1, l, r);
    }

    private int querySum(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) {
            return 0;
        }
        if (l <= tl && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return querySum(2*v, tl, tm, l, r) +
                querySum(2*v+1, tm+1, tr, l, r);
    }

    private void build(int[] a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(a, 2*v, tl, tm);
        build(a, 2*v+1, tm+1, tr);
        t[v] = t[2*v] + t[2*v+1];
    }

    private void update(int v, int tl, int tr, int pos, int newVal) {
        if (tl == tr) {
            t[v] = newVal;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2*v, tl, tm, pos, newVal);
        } else {
            update(2*v+1, tm+1, tr, pos, newVal);
        }
        t[v] = t[2*v] + t[2*v+1];
    }
}

参考

PS

  • 2022-10-07 小改动；新逻辑更加方便书写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    private int querySum(int v, int tl, int tr, int l, int r) {
-       if (l > r) {
+       if (l > tr || r < tl) {
            return 0;
        }
-       if (tl == l && tr == r) {
+       if (l <= tl && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
-       return querySum(2*v, tl, tm, l, Math.min(tm, r)) +
-               querySum(2*v+1, tm+1, tr, Math.max(l, tm+1), r);
+       return querySum(2*v, tl, tm, l, r) +
+               querySum(2*v+1, tm+1, tr, l, r);
    }