跳转至

線段樹

引入

線段樹是算法競賽中常用的用來維護 區間信息 的數據結構。

線段樹可以在 \(O(\log N)\) 的時間複雜度內實現單點修改、區間修改、區間查詢（區間求和，求區間最大值，求區間最小值）等操作。

線段樹

線段樹的基本結構與建樹

過程

線段樹將每個長度不為 \(1\) 的區間劃分成左右兩個區間遞歸求解，把整個線段劃分為一個樹形結構，通過合併左右兩區間信息來求得該區間的信息。這種數據結構可以方便的進行大部分的區間操作。

有個大小為 \(5\) 的數組 \(a=\{10,11,12,13,14\}\)，要將其轉化為線段樹，有以下做法：設線段樹的根節點編號為 \(1\)，用數組 \(d\) 來保存我們的線段樹，\(d_i\) 用來保存線段樹上編號為 \(i\) 的節點的值（這裏每個節點所維護的值就是這個節點所表示的區間總和）。

我們先給出這棵線段樹的形態，如圖所示：

圖中每個節點中用紅色字體標明的區間，表示該節點管轄的 \(a\) 數組上的位置區間。如 \(d_1\) 所管轄的區間就是 \([1,5]\)（\(a_1,a_2, \cdots ,a_5\)），即 \(d_1\) 所保存的值是 \(a_1+a_2+ \cdots +a_5\)，\(d_1=60\) 表示的是 \(a_1+a_2+ \cdots +a_5=60\)。

通過觀察不難發現，\(d_i\) 的左兒子節點就是 \(d_{2\times i}\)，\(d_i\) 的右兒子節點就是 \(d_{2\times i+1}\)。如果 \(d_i\) 表示的是區間 \([s,t]\)（即 \(d_i=a_s+a_{s+1}+ \cdots +a_t\)）的話，那麼 \(d_i\) 的左兒子節點表示的是區間 \([ s, \frac{s+t}{2} ]\)，\(d_i\) 的右兒子表示的是區間 \([ \frac{s+t}{2} +1,t ]\)。

在實現時，我們考慮遞歸建樹。設當前的根節點為 \(p\)，如果根節點管轄的區間長度已經是 \(1\)，則可以直接根據 \(a\) 數組上相應位置的值初始化該節點。否則我們將該區間從中點處分割為兩個子區間，分別進入左右子節點遞歸建樹，最後合併兩個子節點的信息。

實現

此處給出代碼實現，可參考註釋理解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void build(int s, int t, int p) {
  // 對 [s,t] 區間建立線段樹,當前根的編號為 p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // 移位運算符的優先級小於加減法，所以加上括號
  // 如果寫成 (s + t) >> 1 可能會超出 int 範圍
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // 遞歸對左右區間建樹
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def build(s, t, p):
    # 對 [s,t] 區間建立線段樹,當前根的編號為 p
    if s == t:
        d[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    # 移位運算符的優先級小於加減法，所以加上括號
    # 如果寫成 (s + t) >> 1 可能會超出 int 範圍
    build(s, m, p * 2); build(m + 1, t, p * 2 + 1)
    # 遞歸對左右區間建樹
    d[p] = d[p * 2] + d[(p * 2) + 1]

關於線段樹的空間：如果採用堆式存儲（\(2p\) 是 \(p\) 的左兒子，\(2p+1\) 是 \(p\) 的右兒子），若有 \(n\) 個葉子結點，則 d 數組的範圍最大為 \(2^{\left\lceil\log{n}\right\rceil+1}\)。

分析：容易知道線段樹的深度是 \(\left\lceil\log{n}\right\rceil\) 的，則在堆式儲存情況下葉子節點（包括無用的葉子節點）數量為 \(2^{\left\lceil\log{n}\right\rceil}\) 個，又由於其為一棵完全二叉樹，則其總節點個數 \(2^{\left\lceil\log{n}\right\rceil+1}-1\)。當然如果你懶得計算的話可以直接把數組長度設為 \(4n\)，因為 \(\frac{2^{\left\lceil\log{n}\right\rceil+1}-1}{n}\) 的最大值在 \(n=2^{x}+1(x\in N_{+})\) 時取到，此時節點數為 \(2^{\left\lceil\log{n}\right\rceil+1}-1=2^{x+2}-1=4n-5\)。

線段樹的區間查詢

過程

區間查詢，比如求區間 \([l,r]\) 的總和（即 \(a_l+a_{l+1}+ \cdots +a_r\)）、求區間最大值/最小值等操作。

仍然以最開始的圖為例，如果要查詢區間 \([1,5]\) 的和，那直接獲取 \(d_1\) 的值（\(60\)）即可。

如果要查詢的區間為 \([3,5]\)，此時就不能直接獲取區間的值，但是 \([3,5]\) 可以拆成 \([3,3]\) 和 \([4,5]\)，可以通過合併這兩個區間的答案來求得這個區間的答案。

一般地，如果要查詢的區間是 \([l,r]\)，則可以將其拆成最多為 \(O(\log n)\) 個 極大 的區間，合併這些區間即可求出 \([l,r]\) 的答案。

實現

此處給出代碼實現，可參考註釋理解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int getsum(int l, int r, int s, int t, int p) {
  // [l, r] 為查詢區間, [s, t] 為當前節點包含的區間, p 為當前節點的編號
  if (l <= s && t <= r)
    return d[p];  // 當前區間為詢問區間的子集時直接返回當前區間的和
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // 如果左兒子代表的區間 [s, m] 與詢問區間有交集, 則遞歸查詢左兒子
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // 如果右兒子代表的區間 [m + 1, t] 與詢問區間有交集, 則遞歸查詢右兒子
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def getsum(l, r, s, t, p):
    # [l, r] 為查詢區間, [s, t] 為當前節點包含的區間, p 為當前節點的編號
    if l <= s and t <= r:
        return d[p] # 當前區間為詢問區間的子集時直接返回當前區間的和
    m = s + ((t - s) >> 1); sum = 0
    if l <= m:
        sum = sum + getsum(l, r, s, m, p * 2)
    # 如果左兒子代表的區間 [s, m] 與詢問區間有交集, 則遞歸查詢左兒子
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    # 如果右兒子代表的區間 [m + 1, t] 與詢問區間有交集, 則遞歸查詢右兒子
    return sum

線段樹的區間修改與懶惰標記

過程

如果要求修改區間 \([l,r]\)，把所有包含在區間 \([l,r]\) 中的節點都遍歷一次、修改一次，時間複雜度無法承受。我們這裏要引入一個叫做 「懶惰標記」 的東西。

懶惰標記，簡單來説，就是通過延遲對節點信息的更改，從而減少可能不必要的操作次數。每次執行修改時，我們通過打標記的方法表明該節點對應的區間在某一次操作中被更改，但不更新該節點的子節點的信息。實質性的修改則在下一次訪問帶有標記的節點時才進行。

仍然以最開始的圖為例，我們將執行若干次給區間內的數加上一個值的操作。我們現在給每個節點增加一個 \(t_i\)，表示該節點帶的標記值。

最開始時的情況是這樣的（為了節省空間，這裏不再展示每個節點管轄的區間）：

現在我們準備給 \([3,5]\) 上的每個數都加上 \(5\)。根據前面區間查詢的經驗，我們很快找到了兩個極大區間 \([3,3]\) 和 \([4,5]\)（分別對應線段樹上的 \(3\) 號點和 \(5\) 號點）。

我們直接在這兩個節點上進行修改，並給它們打上標記：

我們發現，\(3\) 號節點的信息雖然被修改了（因為該區間管轄兩個數，所以 \(d_3\) 加上的數是 \(5 \times 2=10\)），但它的兩個子節點卻還沒更新，仍然保留着修改之前的信息。不過不用擔心，雖然修改目前還沒進行，但當我們要查詢這兩個子節點的信息時，我們會利用標記修改這兩個子節點的信息，使查詢的結果依舊準確。

接下來我們查詢一下 \([4,4]\) 區間上各數字的和。

我們通過遞歸找到 \([4,5]\) 區間，發現該區間並非我們的目標區間，且該區間上還存在標記。這時候就到標記下放的時間了。我們將該區間的兩個子區間的信息更新，並清除該區間上的標記。

現在 \(6\)、\(7\) 兩個節點的值變成了最新的值，查詢的結果也是準確的。

實現

接下來給出在存在標記的情況下，區間修改和查詢操作的參考實現。

區間修改（區間加上某個值）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void update(int l, int r, int c, int s, int t, int p) {
  // [l, r] 為修改區間, c 為被修改的元素的變化量, [s, t] 為當前節點包含的區間, p
  // 為當前節點的編號
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;
    return;
  }  // 當前區間為修改區間的子集時直接修改當前節點的值,然後打標記,結束脩改
  int m = s + ((t - s) >> 1);
  if (b[p] && s != t) {
    // 如果當前節點的懶標記非空,則更新當前節點兩個子節點的值和懶標記值
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 將標記下傳給子節點
    b[p] = 0;                                // 清空當前節點的標記
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def update(l, r, c, s, t, p):
    # [l, r] 為修改區間, c 為被修改的元素的變化量, [s, t] 為當前節點包含的區間, p
    # 為當前節點的編號
    if l <= s and t <= r:
        d[p] = d[p] + (t - s + 1) * c
        b[p] = b[p] + c
        return
    # 當前區間為修改區間的子集時直接修改當前節點的值, 然後打標記, 結束脩改
    m = s + ((t - s) >> 1)
    if b[p] and s != t:
        # 如果當前節點的懶標記非空, 則更新當前節點兩個子節點的值和懶標記值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 將標記下傳給子節點
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空當前節點的標記
        b[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]

區間查詢（區間求和）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int getsum(int l, int r, int s, int t, int p) {
  // [l, r] 為查詢區間, [s, t] 為當前節點包含的區間, p 為當前節點的編號
  if (l <= s && t <= r) return d[p];
  // 當前區間為詢問區間的子集時直接返回當前區間的和
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    // 如果當前節點的懶標記非空,則更新當前節點兩個子節點的值和懶標記值
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 將標記下傳給子節點
    b[p] = 0;                                // 清空當前節點的標記
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def getsum(l, r, s, t, p):
    # [l, r] 為查詢區間, [s, t] 為當前節點包含的區間, p為當前節點的編號
    if l <= s and t <= r:
        return d[p]
    # 當前區間為詢問區間的子集時直接返回當前區間的和
    m = s + ((t - s) >> 1)
    if b[p]:
        # 如果當前節點的懶標記非空, 則更新當前節點兩個子節點的值和懶標記值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 將標記下傳給子節點
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空當前節點的標記
        b[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    return sum

如果你是要實現區間修改為某一個值而不是加上某一個值的話，代碼如下：

 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
void update(int l, int r, int c, int s, int t, int p) {
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c;
    return;
  }
  int m = s + ((t - s) >> 1);
  // 額外數組儲存是否修改值
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}

int getsum(int l, int r, int s, int t, int p) {
  if (l <= s && t <= r) return d[p];
  int m = s + ((t - s) >> 1);
  if (v[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
    b[p * 2] = b[p * 2 + 1] = b[p];
    v[p * 2] = v[p * 2 + 1] = 1;
    v[p] = 0;
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

 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
def update(l, r, c, s, t, p):
    if l <= s and t <= r:
        d[p] = (t - s + 1) * c
        b[p] = c
        return
    m = s + ((t - s) >> 1)
    if v[p]:
        d[p * 2] = b[p] * (m - s + 1)
        d[p * 2 + 1] = b[p] * (t - m)
        b[p * 2] = b[p * 2 + 1] = b[p]
        v[p * 2] = v[p * 2 + 1] = 1
        v[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]

def getsum(l, r, s, t, p):
    if l <= s and t <= r:
        return d[p]
    m = s + ((t - s) >> 1)
    if v[p]:
        d[p * 2] = b[p] * (m - s + 1)
        d[p * 2 + 1] = b[p] * (t - m)
        b[p * 2] = b[p * 2 + 1] = b[p]
        v[p * 2] = v[p * 2 + 1] = 1
        v[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    return sum

動態開點線段樹

前面講到堆式儲存的情況下，需要給線段樹開 \(4n\) 大小的數組。為了節省空間，我們可以不一次性建好樹，而是在最初只建立一個根結點代表整個區間。當我們需要訪問某個子區間時，才建立代表這個區間的子結點。這樣我們不再使用 \(2p\) 和 \(2p+1\) 代表 \(p\) 結點的兒子，而是用 \(\text{ls}\) 和 \(\text{rs}\) 記錄兒子的編號。總之，動態開點線段樹的核心思想就是：結點只有在有需要的時候才被創建。

單次操作的時間複雜度是不變的，為 \(O(\log n)\)。由於每次操作都有可能創建並訪問全新的一系列結點，因此 \(m\) 次單點操作後結點的數量規模是 \(O(m\log n)\)。最多也只需要 \(2n-1\) 個結點，沒有浪費。

單點修改：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// root 表示整棵線段樹的根結點；cnt 表示當前結點個數
int n, cnt, root;
int sum[n * 2], ls[n * 2], rs[n * 2];

// 用法：update(root, 1, n, x, f); 其中 x 為待修改節點的編號
void update(int& p, int s, int t, int x, int f) {  // 引用傳參
  if (!p) p = ++cnt;  // 當結點為空時，創建一個新的結點
  if (s == t) {
    sum[p] += f;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (x <= m)
    update(ls[p], s, m, x, f);
  else
    update(rs[p], m + 1, t, x, f);
  sum[p] = sum[ls[p]] + sum[rs[p]];  // pushup
}

區間詢問：

1
2
3
4
5
6
7
8
9
// 用法：query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r) {
  if (!p) return 0;  // 如果結點為空，返回 0
  if (s >= l && t <= r) return sum[p];
  int m = s + ((t - s) >> 1), ans = 0;
  if (l <= m) ans += query(ls[p], s, m, l, r);
  if (r > m) ans += query(rs[p], m + 1, t, l, r);
  return ans;
}

區間修改也是一樣的，不過下放標記時要注意如果缺少孩子，就直接創建一個新的孩子。或者使用標記永久化技巧。

一些優化

這裏總結幾個線段樹的優化：

  • 在葉子節點處無需下放懶惰標記，所以懶惰標記可以不下傳到葉子節點。

  • 下放懶惰標記可以寫一個專門的函數 pushdown，從兒子節點更新當前節點也可以寫一個專門的函數 maintain（或者對稱地用 pushup），降低代碼編寫難度。

  • 標記永久化：如果確定懶惰標記不會在中途被加到溢出（即超過了該類型數據所能表示的最大範圍），那麼就可以將標記永久化。標記永久化可以避免下傳懶惰標記，只需在進行詢問時把標記的影響加到答案當中，從而降低程序常數。具體如何處理與題目特性相關，需結合題目來寫。這也是樹套樹和可持久化數據結構中會用到的一種技巧。

C++ 模板

SegTreeLazyRangeAdd 可以區間加/求和的線段樹模板 
 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
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTreeLazyRangeAdd {
  vector<T> tree, lazy;
  vector<T> *arr;
  int n, root, n4, end;

  void maintain(int cl, int cr, int p) {
    int cm = cl + (cr - cl) / 2;
    if (cl != cr && lazy[p]) {
      lazy[p * 2] += lazy[p];
      lazy[p * 2 + 1] += lazy[p];
      tree[p * 2] += lazy[p] * (cm - cl + 1);
      tree[p * 2 + 1] += lazy[p] * (cr - cm);
      lazy[p] = 0;
    }
  }

  T range_sum(int l, int r, int cl, int cr, int p) {
    if (l <= cl && cr <= r) return tree[p];
    int m = cl + (cr - cl) / 2;
    T sum = 0;
    maintain(cl, cr, p);
    if (l <= m) sum += range_sum(l, r, cl, m, p * 2);
    if (r > m) sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
    return sum;
  }

  void range_add(int l, int r, T val, int cl, int cr, int p) {
    if (l <= cl && cr <= r) {
      lazy[p] += val;
      tree[p] += (cr - cl + 1) * val;
      return;
    }
    int m = cl + (cr - cl) / 2;
    maintain(cl, cr, p);
    if (l <= m) range_add(l, r, val, cl, m, p * 2);
    if (r > m) range_add(l, r, val, m + 1, cr, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

  void build(int s, int t, int p) {
    if (s == t) {
      tree[p] = (*arr)[s];
      return;
    }
    int m = s + (t - s) / 2;
    build(s, m, p * 2);
    build(m + 1, t, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

 public:
  explicit SegTreeLazyRangeAdd<T>(vector<T> v) {
    n = v.size();
    n4 = n * 4;
    tree = vector<T>(n4, 0);
    lazy = vector<T>(n4, 0);
    arr = &v;
    end = n - 1;
    root = 1;
    build(0, end, 1);
    arr = nullptr;
  }

  void show(int p, int depth = 0) {
    if (p > n4 || tree[p] == 0) return;
    show(p * 2, depth + 1);
    for (int i = 0; i < depth; ++i) putchar('\t');
    printf("%d:%d\n", tree[p], lazy[p]);
    show(p * 2 + 1, depth + 1);
  }

  T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }

  void range_add(int l, int r, int val) { range_add(l, r, val, 0, end, root); }
};
SegTreeLazyRangeSet 可以區間修改/求和的線段樹模板 
 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
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class SegTreeLazyRangeSet {
  vector<T> tree, lazy;
  vector<T> *arr;
  int n, root, n4, end;

  void maintain(int cl, int cr, int p) {
    int cm = cl + (cr - cl) / 2;
    if (cl != cr && lazy[p]) {
      lazy[p * 2] = lazy[p];
      lazy[p * 2 + 1] = lazy[p];
      tree[p * 2] = lazy[p] * (cm - cl + 1);
      tree[p * 2 + 1] = lazy[p] * (cr - cm);
      lazy[p] = 0;
    }
  }

  T range_sum(int l, int r, int cl, int cr, int p) {
    if (l <= cl && cr <= r) return tree[p];
    int m = cl + (cr - cl) / 2;
    T sum = 0;
    maintain(cl, cr, p);
    if (l <= m) sum += range_sum(l, r, cl, m, p * 2);
    if (r > m) sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
    return sum;
  }

  void range_set(int l, int r, T val, int cl, int cr, int p) {
    if (l <= cl && cr <= r) {
      lazy[p] = val;
      tree[p] = (cr - cl + 1) * val;
      return;
    }
    int m = cl + (cr - cl) / 2;
    maintain(cl, cr, p);
    if (l <= m) range_set(l, r, val, cl, m, p * 2);
    if (r > m) range_set(l, r, val, m + 1, cr, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

  void build(int s, int t, int p) {
    if (s == t) {
      tree[p] = (*arr)[s];
      return;
    }
    int m = s + (t - s) / 2;
    build(s, m, p * 2);
    build(m + 1, t, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
  }

 public:
  explicit SegTreeLazyRangeSet<T>(vector<T> v) {
    n = v.size();
    n4 = n * 4;
    tree = vector<T>(n4, 0);
    lazy = vector<T>(n4, 0);
    arr = &v;
    end = n - 1;
    root = 1;
    build(0, end, 1);
    arr = nullptr;
  }

  void show(int p, int depth = 0) {
    if (p > n4 || tree[p] == 0) return;
    show(p * 2, depth + 1);
    for (int i = 0; i < depth; ++i) putchar('\t');
    printf("%d:%d\n", tree[p], lazy[p]);
    show(p * 2 + 1, depth + 1);
  }

  T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }

  void range_set(int l, int r, int val) { range_set(l, r, val, 0, end, root); }
};

例題

luogu P3372【模板】線段樹 1

已知一個數列，你需要進行下面兩種操作：

  • 將某區間每一個數加上 \(k\)。
  • 求出某區間每一個數的和。
參考代碼 
 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
#include <iostream>
typedef long long LL;
LL n, a[100005], d[270000], b[270000];

void build(LL l, LL r, LL p) {  // l:区间左端点 r:区间右端点 p:节点标号
  if (l == r) {
    d[p] = a[l];  // 将节点赋值
    return;
  }
  LL m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);  // 分别建立子树
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(LL l, LL r, LL c, LL s, LL t, LL p) {
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;  // 如果区间被包含了，直接得出答案
    return;
  }
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  if (l <= m)
    update(l, r, c, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的节点
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];  // 计算该节点区间和
}

LL getsum(LL l, LL r, LL s, LL t, LL p) {
  if (l <= s && t <= r) return d[p];
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  LL sum = 0;
  if (l <= m)
    sum =
        getsum(l, r, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的答案
  if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
  return sum;
}

int main() {
  std::ios::sync_with_stdio(0);
  LL q, i1, i2, i3, i4;
  std::cin >> n >> q;
  for (LL i = 1; i <= n; i++) std::cin >> a[i];
  build(1, n, 1);
  while (q--) {
    std::cin >> i1 >> i2 >> i3;
    if (i1 == 2)
      std::cout << getsum(i2, i3, 1, n, 1) << std::endl;  // 直接调用操作函数
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}
luogu P3373【模板】線段樹 2

已知一個數列，你需要進行下面三種操作：

  • 將某區間每一個數乘上 \(x\)。
  • 將某區間每一個數加上 \(x\)。
  • 求出某區間每一個數的和。
參考代碼 
  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
130
131
132
133
#include <cstdio>
#define ll long long

ll read() {
  ll w = 1, q = 0;
  char ch = ' ';
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') q = (ll)q * 10 + ch - '0', ch = getchar();
  return (ll)w * q;
}

int n, m;
ll mod;
ll a[100005], sum[400005], mul[400005], laz[400005];

void up(int i) { sum[i] = (sum[(i << 1)] + sum[(i << 1) | 1]) % mod; }

void pd(int i, int s, int t) {
  int l = (i << 1), r = (i << 1) | 1, mid = (s + t) >> 1;
  if (mul[i] != 1) {  // 懒标记传递，两个懒标记
    mul[l] *= mul[i];
    mul[l] %= mod;
    mul[r] *= mul[i];
    mul[r] %= mod;
    laz[l] *= mul[i];
    laz[l] %= mod;
    laz[r] *= mul[i];
    laz[r] %= mod;
    sum[l] *= mul[i];
    sum[l] %= mod;
    sum[r] *= mul[i];
    sum[r] %= mod;
    mul[i] = 1;
  }
  if (laz[i]) {  // 懒标记传递
    sum[l] += laz[i] * (mid - s + 1);
    sum[l] %= mod;
    sum[r] += laz[i] * (t - mid);
    sum[r] %= mod;
    laz[l] += laz[i];
    laz[l] %= mod;
    laz[r] += laz[i];
    laz[r] %= mod;
    laz[i] = 0;
  }
  return;
}

void build(int s, int t, int i) {
  mul[i] = 1;
  if (s == t) {
    sum[i] = a[s];
    return;
  }
  int mid = s + ((t - s) >> 1);
  build(s, mid, i << 1);  // 建树
  build(mid + 1, t, (i << 1) | 1);
  up(i);
}

void chen(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    mul[i] *= z;
    mul[i] %= mod;  // 这是取模的
    laz[i] *= z;
    laz[i] %= mod;  // 这是取模的
    sum[i] *= z;
    sum[i] %= mod;  // 这是取模的
    return;
  }
  pd(i, s, t);
  if (mid >= l) chen(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) chen(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

void add(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    sum[i] += z * (t - s + 1);
    sum[i] %= mod;  // 这是取模的
    laz[i] += z;
    laz[i] %= mod;  // 这是取模的
    return;
  }
  pd(i, s, t);
  if (mid >= l) add(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) add(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

ll getans(int l, int r, int s, int t,
          int i) {  // 得到答案，可以看下上面懒标记助于理解
  int mid = s + ((t - s) >> 1);
  ll tot = 0;
  if (l <= s && t <= r) return sum[i];
  pd(i, s, t);
  if (mid >= l) tot += getans(l, r, s, mid, (i << 1));
  tot %= mod;
  if (mid + 1 <= r) tot += getans(l, r, mid + 1, t, (i << 1) | 1);
  return tot % mod;
}

int main() {  // 读入
  int i, j, x, y, bh;
  ll z;
  n = read();
  m = read();
  mod = read();
  for (i = 1; i <= n; i++) a[i] = read();
  build(1, n, 1);  // 建树
  for (i = 1; i <= m; i++) {
    bh = read();
    if (bh == 1) {
      x = read();
      y = read();
      z = read();
      chen(x, y, 1, n, 1, z);
    } else if (bh == 2) {
      x = read();
      y = read();
      z = read();
      add(x, y, 1, n, 1, z);
    } else if (bh == 3) {
      x = read();
      y = read();
      printf("%lld\n", getans(x, y, 1, n, 1));
    }
  }
  return 0;
}
HihoCoder 1078 線段樹的區間修改

假設貨架上從左到右擺放了 \(N\) 種商品，並且依次標號為 \(1\) 到 \(N\)，其中標號為 \(i\) 的商品的價格為 \(Pi\)。小 Hi 的每次操作分為兩種可能，第一種是修改價格：小 Hi 給出一段區間 \([L, R]\) 和一個新的價格 \(\textit{NewP}\)，所有標號在這段區間中的商品的價格都變成 \(\textit{NewP}\)。第二種操作是詢問：小 Hi 給出一段區間 \([L, R]\)，而小 Ho 要做的便是計算出所有標號在這段區間中的商品的總價格，然後告訴小 Hi。

參考代碼 
 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
#include <iostream>

int n, a[100005], d[270000], b[270000];

void build(int l, int r, int p) {  // 建树
  if (l == r) {
    d[p] = a[l];
    return;
  }
  int m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(int l, int r, int c, int s, int t,
            int p) {  // 更新，可以参考前面两个例题
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c;
    return;
  }
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
    b[p << 1] = b[(p << 1) | 1] = b[p];
    b[p] = 0;
  }
  if (l <= m) update(l, r, c, s, m, p << 1);
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

int getsum(int l, int r, int s, int t, int p) {  // 取得答案，和前面一样
  if (l <= s && t <= r) return d[p];
  int m = s + ((t - s) >> 1);
  if (b[p]) {
    d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
    b[p << 1] = b[(p << 1) | 1] = b[p];
    b[p] = 0;
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p << 1);
  if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
  return sum;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin >> n;
  for (int i = 1; i <= n; i++) std::cin >> a[i];
  build(1, n, 1);
  int q, i1, i2, i3, i4;
  std::cin >> q;
  while (q--) {
    std::cin >> i1 >> i2 >> i3;
    if (i1 == 0)
      std::cout << getsum(i2, i3, 1, n, 1) << std::endl;
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}
2018 Multi-University Training Contest 5 Problem G. Glad You Came
解題思路

維護一下每個區間的永久標記就可以了，最後在線段樹上跑一邊 DFS 統計結果即可。注意打標記的時候加個剪枝優化，否則會 TLE。

線段樹合併

過程

顧名思義，線段樹合併是指建立一棵新的線段樹，這棵線段樹的每個節點都是兩棵原線段樹對應節點合併後的結果。它常常被用於維護樹上或是圖上的信息。

顯然，我們不可能真的每次建滿一顆新的線段樹，因此我們需要使用上文的動態開點線段樹。

線段樹合併的過程本質上相當暴力：

假設兩顆線段樹為 A 和 B，我們從 1 號節點開始遞歸合併。

遞歸到某個節點時，如果 A 樹或者 B 樹上的對應節點為空，直接返回另一個樹上對應節點，這裏運用了動態開點線段樹的特性。

如果遞歸到葉子節點，我們合併兩棵樹上的對應節點。

最後，根據子節點更新當前節點並且返回。

線段樹合併的複雜度

顯然，對於兩顆滿的線段樹，合併操作的複雜度是 \(O(n\log n)\) 的。但實際情況下使用的常常是權值線段樹，總點數和 \(n\) 的規模相差並不大。並且合併時一般不會重複地合併某個線段樹，所以我們最終增加的點數大致是 \(n\log n\) 級別的。這樣，總的複雜度就是 \(O(n\log n)\) 級別的。當然，在一些情況下，可並堆可能是更好的選擇。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int merge(int a, int b, int l, int r) {
  if (!a) return b;
  if (!b) return a;
  if (l == r) {
    // do something...
    return a;
  }
  int mid = (l + r) >> 1;
  tr[a].l = merge(tr[a].l, tr[b].l, l, mid);
  tr[a].r = merge(tr[a].r, tr[b].r, mid + 1, r);
  pushup(a);
  return a;
}

例題

luogu P4556 [Vani 有約會] 雨天的尾巴/【模板】線段樹合併
解題思路

線段樹合併模板題，用差分把樹上修改轉化為單點修改，然後向上 dfs 線段樹合併統計答案即可。

參考代碼 
  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
#include <bits/stdc++.h>
using namespace std;
int n, fa[100005][22], dep[100005], rt[100005];
int sum[5000005], cnt = 0, res[5000005], ls[5000005], rs[5000005];
int m, ans[100005];
vector<int> v[100005];

void update(int x) {
  if (sum[ls[x]] < sum[rs[x]]) {
    res[x] = res[rs[x]];
    sum[x] = sum[rs[x]];
  } else {
    res[x] = res[ls[x]];
    sum[x] = sum[ls[x]];
  }
}

int merge(int a, int b, int x, int y) {
  if (!a) return b;
  if (!b) return a;
  if (x == y) {
    sum[a] += sum[b];
    return a;
  }
  int mid = (x + y) >> 1;
  ls[a] = merge(ls[a], ls[b], x, mid);
  rs[a] = merge(rs[a], rs[b], mid + 1, y);
  update(a);
  return a;
}

int add(int id, int x, int y, int co, int val) {
  if (!id) id = ++cnt;
  if (x == y) {
    sum[id] += val;
    res[id] = co;
    return id;
  }
  int mid = (x + y) >> 1;
  if (co <= mid)
    ls[id] = add(ls[id], x, mid, co, val);
  else
    rs[id] = add(rs[id], mid + 1, y, co, val);
  update(id);
  return id;
}

void initlca(int x) {
  for (int i = 0; i <= 20; i++) fa[x][i + 1] = fa[fa[x][i]][i];
  for (int i : v[x]) {
    if (i == fa[x][0]) continue;
    dep[i] = dep[x] + 1;
    fa[i][0] = x;
    initlca(i);
  }
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int d = dep[x] - dep[y], i = 0; d; d >>= 1, i++)
    if (d & 1) x = fa[x][i];
  if (x == y) return x;
  for (int i = 20; i >= 0; i--)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}

void cacl(int x) {
  for (int i : v[x]) {
    if (i == fa[x][0]) continue;
    cacl(i);
    rt[x] = merge(rt[x], rt[i], 1, 100000);
  }
  ans[x] = res[rt[x]];
  if (sum[rt[x]] == 0) ans[x] = 0;
}

int main() {
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  initlca(1);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    rt[a] = add(rt[a], 1, 100000, c, 1);
    rt[b] = add(rt[b], 1, 100000, c, 1);
    int t = lca(a, b);
    rt[t] = add(rt[t], 1, 100000, c, -1);
    rt[fa[t][0]] = add(rt[fa[t][0]], 1, 100000, c, -1);
  }
  cacl(1);
  for (int i = 1; i <= n; i++) cout << ans[i] << endl;
  return 0;
}

線段樹分裂

過程

線段樹分裂實質上是線段樹合併的逆過程。線段樹分裂只適用於有序的序列，無序的序列是沒有意義的，常用在動態開點的權值線段樹。

注意當分裂和合並都存在時，我們在合併的時候必須回收節點，以避免分裂時會可能出現節點重複佔用的問題。

從一顆區間為 \([1,N]\) 的線段樹中分裂出 \([l,r]\)，建一顆新的樹：

從 1 號結點開始遞歸分裂，當節點不存在或者代表的區間 \([s,t]\) 與 \([l,r]\) 沒有交集時直接回溯。

當 \([s,t]\) 與 \([l,r]\) 有交集時需要開一個新結點。

當 \([s,t]\) 包含於 \([l,r]\) 時，需要將當前結點直接接到新的樹下面，並把舊邊斷開。

線段樹分裂的複雜度

可以發現被斷開的邊最多隻會有 \(\log n\) 條，所以最終每次分裂的時間複雜度就是 \(O(\log⁡ n)\)，相當於區間查詢的複雜度。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void split(int &p, int &q, int s, int t, int l, int r) {
  if (t < l || r < s) return;
  if (!p) return;
  if (l <= s && t <= r) {
    q = p;
    p = 0;
    return;
  }
  if (!q) q = New();
  int m = s + t >> 1;
  if (l <= m) split(ls[p], ls[q], s, m, l, r);
  if (m < r) split(rs[p], rs[q], m + 1, t, l, r);
  push_up(p);
  push_up(q);
}

例題

P5494【模板】線段樹分裂
解題思路

線段樹分裂模板題，將 \([x,y]\) 分裂出來。

  • 將 \(t\) 樹合併入 \(p\) 樹：單次合併即可。
  • \(p\) 樹中插入 \(x\) 個 \(q\)：單點修改。
  • 查詢 \([x,y]\) 中數的個數：區間求和。
  • 查詢第 \(k\) 小。
參考代碼 
  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
130
131
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int idx = 1;
long long sum[N << 5];
int ls[N << 5], rs[N << 5], root[N << 2], rub[N << 5], cnt, tot;

// 内存分配与回收
int New() { return cnt ? rub[cnt--] : ++tot; }

void Del(int &p) {
  ls[p] = rs[p] = sum[p] = 0;
  rub[++cnt] = p;
  p = 0;
}

void push_up(int p) { sum[p] = sum[ls[p]] + sum[rs[p]]; }

void build(int s, int t, int &p) {
  if (!p) p = New();
  if (s == t) {
    cin >> sum[p];
    return;
  }
  int m = s + t >> 1;
  build(s, m, ls[p]);
  build(m + 1, t, rs[p]);
  push_up(p);
}

// 单点修改
void update(int x, int c, int s, int t, int &p) {
  if (!p) p = New();
  if (s == t) {
    sum[p] += c;
    return;
  }
  int m = s + t >> 1;
  if (x <= m)
    update(x, c, s, m, ls[p]);
  else
    update(x, c, m + 1, t, rs[p]);
  push_up(p);
}

// 合并
int merge(int p, int q, int s, int t) {
  if (!p || !q) return p + q;
  if (s == t) {
    sum[p] += sum[q];
    Del(q);
    return p;
  }
  int m = s + t >> 1;
  ls[p] = merge(ls[p], ls[q], s, m);
  rs[p] = merge(rs[p], rs[q], m + 1, t);
  push_up(p);
  Del(q);
  return p;
}

// 分裂
void split(int &p, int &q, int s, int t, int l, int r) {
  if (t < l || r < s) return;
  if (!p) return;
  if (l <= s && t <= r) {
    q = p;
    p = 0;
    return;
  }
  if (!q) q = New();
  int m = s + t >> 1;
  if (l <= m) split(ls[p], ls[q], s, m, l, r);
  if (m < r) split(rs[p], rs[q], m + 1, t, l, r);
  push_up(p);
  push_up(q);
}

long long query(int l, int r, int s, int t, int p) {
  if (!p) return 0;
  if (l <= s && t <= r) return sum[p];
  int m = s + t >> 1;
  long long ans = 0;
  if (l <= m) ans += query(l, r, s, m, ls[p]);
  if (m < r) ans += query(l, r, m + 1, t, rs[p]);
  return ans;
}

int kth(int s, int t, int k, int p) {
  if (s == t) return s;
  int m = s + t >> 1;
  long long left = sum[ls[p]];
  if (k <= left)
    return kth(s, m, k, ls[p]);
  else
    return kth(m + 1, t, k - left, rs[p]);
}

int main() {
  cin >> n >> m;
  build(1, n, root[1]);
  while (m--) {
    int op;
    cin >> op;
    if (!op) {
      int p, x, y;
      cin >> p >> x >> y;
      split(root[p], root[++idx], 1, n, x, y);
    } else if (op == 1) {
      int p, t;
      cin >> p >> t;
      root[p] = merge(root[p], root[t], 1, n);
    } else if (op == 2) {
      int p, x, q;
      cin >> p >> x >> q;
      update(q, x, 1, n, root[p]);
    } else if (op == 3) {
      int p, x, y;
      cin >> p >> x >> y;
      cout << query(x, y, 1, n, root[p]) << endl;
    } else {
      int p, k;
      cin >> p >> k;
      if (sum[root[p]] < k)
        cout << -1 << endl;
      else
        cout << kth(1, n, k, root[p]) << endl;
    }
  }
}

線段樹優化建圖

在建圖連邊的過程中，我們有時會碰到這種題目，一個點向一段連續的區間中的點連邊或者一個連續的區間向一個點連邊，如果我們真的一條一條連過去，那一旦點的數量多了複雜度就爆炸了，這裏就需要用線段樹的區間性質來優化我們的建圖了。

下面是一個線段樹。

每個節點都代表了一個區間，假設我們要向區間 \([2, 4]\) 連邊。

在一些題目中，還會出現一個區間連向一個點的情況，則我們將上面第一張圖的有向邊全部反過來即可，上面的樹叫做入樹，下面這個叫做出樹。

Legacy

題目大意：有 \(n\) 個點、\(q\) 次操作。每一種操作為以下三種類型中的一種：

  • 操作一：連一條 \(u \rightarrow v\) 的有向邊，權值為 \(w\)。
  • 操作二：對於所有 \(i \in [l,r]\) 連一條 \(u \rightarrow i\) 的有向邊，權值為 \(w\)。
  • 操作三：對於所有 \(i \in [l,r]\) 連一條 \(i \rightarrow u\) 的有向邊，權值為 \(w\)。

求從點 \(s\) 到其他點的最短路。

\(1 \le n,q \le 10^5, 1 \le w \le 10^9\)。

參考代碼 
  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
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

using pil = pair<int, ll>;
using pli = pair<ll, int>;

int n, q, s, tot, rt1, rt2;
int pos[N];
ll dis[N << 3];
vector<pil> e[N << 3];
bitset<(N << 3)> vis;

struct seg {
  int l, r, lson, rson;
} t[N << 3];

inline int ls(int u) {  // 左儿子
  return t[u].lson;
}

inline int rs(int u) {  // 右儿子
  return t[u].rson;
}

void build(int &u, int l, int r) {  // 动态开点建造入树
  u = ++tot;
  t[u] = seg{l, r};
  if (l == r) {
    pos[l] = u;
    return;
  }
  int mid = (l + r) >> 1;
  build(t[u].lson, l, mid);
  build(t[u].rson, mid + 1, r);
  e[u].emplace_back(ls(u), 0);
  e[u].emplace_back(rs(u), 0);
}

void build2(int &u, int l, int r) {  // 动态开点建造出树
  if (l == r) {
    u = pos[l];
    return;
  }
  u = ++tot;
  t[u] = seg{l, r};
  int mid = (l + r) >> 1;
  build2(t[u].lson, l, mid);
  build2(t[u].rson, mid + 1, r);
  e[ls(u)].emplace_back(u, 0);
  e[rs(u)].emplace_back(u, 0);
}

void add1(int u, int lr, int rr, int v, ll w) {  // 点向区间连边
  if (lr <= t[u].l && t[u].r <= rr) {
    e[v].emplace_back(u, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add1(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add1(rs(u), lr, rr, v, w);
  }
}

void add2(int u, int lr, int rr, int v, ll w) {  // 区间向点连边
  if (lr <= t[u].l && t[u].r <= rr) {
    e[u].emplace_back(v, w);
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (lr <= mid) {
    add2(ls(u), lr, rr, v, w);
  }
  if (rr > mid) {
    add2(rs(u), lr, rr, v, w);
  }
}

void dij(int S) {
  priority_queue<pli, vector<pli>, greater<pli> > q;
  int tot = (n << 2);
  for (int i = 1; i <= tot; ++i) {
    dis[i] = 1e18;
  }
  dis[S] = 0;
  q.emplace(dis[S], S);
  while (!q.empty()) {
    pli fr = q.top();
    q.pop();
    int u = fr.second;
    if (vis[u]) continue;
    for (pil it : e[u]) {
      int v = it.first;
      ll w = it.second;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.emplace(dis[v], v);
      }
    }
  }
}

int main() {
  scanf("%d%d%d", &n, &q, &s);
  build(rt1, 1, n);
  build2(rt2, 1, n);
  for (int i = 1, op, u; i <= q; ++i) {
    scanf("%d%d", &op, &u);
    if (op == 1) {
      int v;
      ll w;
      scanf("%d%lld", &v, &w);
      e[pos[u]].emplace_back(pos[v], w);
    } else if (op == 2) {
      int l, r;
      ll w;
      scanf("%d%d%lld", &l, &r, &w);
      add1(rt1, l, r, pos[u], w);
    } else {
      int l, r;
      ll w;
      scanf("%d%d%lld", &l, &r, &w);
      add2(rt2, l, r, pos[u], w);
    }
  }
  dij(pos[s]);
  for (int i = 1; i <= n; ++i) {
    if (dis[pos[i]] == 1e18) {
      printf("-1 ");
    } else {
      printf("%lld ", dis[pos[i]]);
    }
  }
  return 0;
}

拓展 - 貓樹

眾所周知線段樹可以支持高速查詢某一段區間的信息和，比如區間最大子段和，區間和，區間矩陣的連乘積等等。

但是有一個問題在於普通線段樹的區間詢問在某些毒瘤的眼裏可能還是有些慢了。

簡單來説就是線段樹建樹的時候需要做 \(O(n)\) 次合併操作，而每一次區間詢問需要做 \(O(\log{n})\) 次合併操作，詢問區間和這種東西的時候還可以忍受，但是當我們需要詢問區間線性基這種合併複雜度高達 \(O(\log^2{w})\) 的信息的話，此時就算是做 \(O(\log{n})\) 次合併有些時候在時間上也是不可接受的。

而所謂「貓樹」就是一種不支持修改，僅僅支持快速區間詢問的一種靜態線段樹。

構造一棵這樣的靜態線段樹需要 \(O(n\log{n})\) 次合併操作，但是此時的查詢複雜度被加速至 \(O(1)\) 次合併操作。

在處理線性基這樣特殊的信息的時候甚至可以將複雜度降至 \(O(n\log^2{w})\)。

原理

在查詢 \([l,r]\) 這段區間的信息和的時候，將線段樹樹上代表 \([l,l]\) 的節點和代表 \([r,r]\) 這段區間的節點在線段樹上的 LCA 求出來，設這個節點 \(p\) 代表的區間為 \([L,R]\)，我們會發現一些非常有趣的性質：

  1. \([L,R]\) 這個區間一定包含 \([l,r]\)。顯然，因為它既是 \(l\) 的祖先又是 \(r\) 的祖先。

  2. \([l,r]\) 這個區間一定跨越 \([L,R]\) 的中點。由於 \(p\) 是 \(l\) 和 \(r\) 的 LCA，這意味着 \(p\) 的左兒子是 \(l\) 的祖先而不是 \(r\) 的祖先，\(p\) 的右兒子是 \(r\) 的祖先而不是 \(l\) 的祖先。因此，\(l\) 一定在 \([L,\mathit{mid}]\) 這個區間內，\(r\) 一定在 \((\mathit{mid},R]\) 這個區間內。

有了這兩個性質，我們就可以將詢問的複雜度降至 \(O(1)\) 了。

實現

具體來講我們建樹的時候對於線段樹樹上的一個節點，設它代表的區間為 \((l,r]\)。

不同於傳統線段樹在這個節點裏只保留 \([l,r]\) 的和，我們在這個節點裏面額外保存 \((l,\mathit{mid}]\) 的後綴和數組和 \((\mathit{mid},r]\) 的前綴和數組。

這樣的話建樹的複雜度為 \(T(n)=2T(n/2)+O(n)=O(n\log{n})\) 同理空間複雜度也從原來的 \(O(n)\) 變成了 \(O(n\log{n})\)。

下面是最關鍵的詢問了。

如果我們詢問的區間是 \([l,r]\) 那麼我們把代表 \([l,l]\) 的節點和代表 \([r,r]\) 的節點的 LCA 求出來，記為 \(p\)。

根據剛才的兩個性質，\(l,r\) 在 \(p\) 所包含的區間之內並且一定跨越了 \(p\) 的中點。

這意味這一個非常關鍵的事實是我們可以使用 \(p\) 裏面的前綴和數組和後綴和數組，將 \([l,r]\) 拆成 \([l,\mathit{mid}]+(\mathit{mid},r]\) 從而拼出來 \([l,r]\) 這個區間。

而這個過程僅僅需要 \(O(1)\) 次合併操作！

不過我們好像忽略了點什麼？

似乎求 LCA 的複雜度似乎還不是 \(O(1)\)，暴力求是 \(O(\log{n})\) 的，倍增法則是 \(O(\log{\log{n}})\) 的，轉 ST 表的代價又太大……

堆式建樹

具體來將我們將這個序列補成 \(2\) 的整次冪，然後建線段樹。

此時我們發現線段樹上兩個節點的 LCA 編號，就是兩個節點二進制編號的最長公共前綴 LCP。

稍作思考即可發現發現在 \(x\) 和 \(y\) 的二進制下 lcp(x,y)=x>>log[x^y]。

所以我們預處理一個 log 數組即可輕鬆完成求 LCA 的工作。

這樣我們就構建了一個貓樹。

由於建樹的時候涉及到求前綴和和求後綴和，所以對於線性基這種雖然合併是 \(O(\log^2{w})\) 但是求前綴和卻是 \(O(n\log{n})\) 的信息，使用貓樹可以將靜態區間線性基從 \(O(n\log^2{w}+m\log^2{w}\log{n})\) 優化至 \(O(n\log{n}\log{w}+m\log^2{w})\) 的複雜度。

參考

  • immortalCO 大爺的博客
  • [Kle77] V. Klee, "Can the Measure of be Computed in Less than O (n log n) Steps?," Am. Math. Mon., vol. 84, no. 4, pp. 284–285, Apr. 1977.
  • [BeW80] Bentley and Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. Comput., vol. C–29, no. 7, pp. 571–577, Jul. 1980.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Marcythm, Ir1d, Ycrpro, Xeonacid, konnyakuxzy, CJSoft, HeRaNO, ethan-enhe, ChungZH, Chrogeek, hsfzLZH1, billchenchina, orzAtalod, luoguojie, Early0v0, wy-luke
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用