2020 競技程設教材 HackMD Book

2020 Week 9: Data Structures

本篇將介紹些 CP 值較高的資料結構

其中 C 代表的是 coding 複雜度，或把 CP 譯作競程

Sparse Table: RMQ

RMQ 全名 Range Maximum/Minimum Query

給定長度

$n$ 的數列

$a$，查詢任意區間極(最大/最小)值

樸素的枚舉區間會有

$O(n^2)$ 的查詢複雜度

不失一般性，下面只以找最大值為例

定義狀態

$ST(i,k)$ 表示數列從

$i$ 位置開始，長度

$2^k$ 區間

$[i,i+2^k)$ 所有數中最大值

例如

$a=(1,2,5,7,2)$ 則

$ST(1,1)=5$，位置從

$0$ 開始

最大值可從更小的長度

$2^{k-1}$ 兩個區間比較得來，起點分別在

$i$ 與

$i+2^{k-1}$
則狀態轉移為

$ST(i,k)=max(ST(i,k-1),ST(i+2^{k-1},k-1))$

而邊界為長度

$1=2^0$ 區間

$ST(i,0)=a_i$

for(int i = 0; i < n; i++) ST[i][0] = a[i];

for(int k = 1; k <= log2(n); k++)
  for(int i = 0; i+(1<<k) <= n; i++)
    ST[i][k] = max(ST[i][k-1], ST[i+(1<<k-1)][k-1]);

建構 Sparse Table 的時間複雜度為

$O(n\cdot {\log }_{2}n)$

如此能利用

$k=\lfloor {\log }_2(R-L)\rfloor ,max(ST(L,k),ST(R-2^k,k)$ 求得區間

$[L,R)$ 的最大值

注意這裡區間表示方式是左閉右開符號

練習：

ZEROJUDGE d539 區間 MAX
TIOJ 1603 胖胖殺蚯事件

---

線段樹 (Range/Interval/Segment Tree)

線段樹是各種區間問題的絕招，相較其他延伸應用 本節只是冰山一角
建議先熟悉第三週的分治法以及第五週的合併排序法再閱讀本節

先考慮一個非常眼熟(?)的問題

給定數列

$a$，有

$Q$ 個操作包括：更新數列上的值或是查詢一個解

針對更新哪些值，以及查詢哪些解，精確的分類可分為：

• 單點更新/單點查詢
• 單點更新/區間查詢
• 區間更新/單點查詢
• 區間更新/區間查詢

而所謂要求的解(答案)可能有：

• 極大/小值
• 總和 (或其他運算結果)

線段樹，顧名思義就是以保存很多區間解的一顆樹，例如數列長度

$5$：

(注意這裡區間表示方式是左閉右開符號)

單點更新/區間查詢

先明確的以簡單的問題設計簡單的線段樹

給定長度

$N$ 的數列

$a$，有

$Q$ 個操作包括：

• 將數列上的一個數加上
  $d_i$
• 查詢一個區間的總和

例如

$a=(1,15,3,7,4)$，

$Q=3$ 筆詢問為：
將

$a_2$ 加上

$5$ 則

$a=(1,20,3,7,4)$
將

$a_5$ 加上

$1$ 則

$a=(1,20,3,7,5)$
詢問區間

$[2,5)$ 的值，則區間總和為

$30$

Node

線段樹的節點保存該區間的解，以及左右子節點的位置

struct node {
  int sum;
  node *lc, *rc; // left child, right child
  node() { sum = 0; lc = rc = NULL; }
};

Build

根據給定數列把初始線段樹造出來

node* build(int L, int R) {
  node* u = new node();
  if(R-L == 1) { // 區間中只剩一個數，也就是葉節點
    u->sum = a[L];
  } else {
    int M = (L+R) / 2;
    u->lc = build(L, M); // 左子樹
    u->rc = build(M, R); // 右子樹
    
    u->sum = u->lc->sum + u->rc->sum;
  }
  
  return u;
}

以

$a=(1,15,3,7,4)$ 為例，線段樹會長這樣

區間旁的數代表總和，例如區間

$[4,6)$ 的總和為

$11$

Update

將數列中某位置

$i$ 的數加上

$d$

void update(node* u, int L, int R, int i, int d) {
  if(i < L || R <= i) return; // 未包含欲更新位置
  u->sum += d;
  
  if(R-L == 1) return; // 葉節點
  
  int M = (L+R) / 2;
  update(u->lc, L, M, i, d);
  update(u->rc, M, R, i, d);
}

以前個樹為例，將

$a_2$ 加上

$5$：

每次只往包含

$i=2$ 位置的區間遞迴下去，複雜度為

$O({\log }_{2}N)$

Query

查詢區間

$[qL,qR)$ 的總和

int query(node* u, int L, int R, int qL, int qR) {
  if(R <= qL || qR <= L) return 0; // 不在欲查詢區間內
  if(qL <= L && R <= qR) return u->sum;
  
  int M = (L+R) / 2;
  return query(u->lc, L, M, qL, qR) + query(u->rc, M, R, qL, qR);
}

以前個樹為例，詢問區間

$[2,5)$ 的總和：

這樣的遞迴查詢，每一層最多只會往下遞迴兩個節點，所以複雜度為

$O({\log }_{2}N)$

利用反證法能證明當某層往下遞迴超過兩個節點會出現矛盾

練習：

HDU OJ 1166 敌兵布阵
CODEFORCES 339D Xenia and Bit Operations
*CODEFORCES 1253E Antenna Coverage

區間更新/區間查詢

變得棘手一些的問題

給定長度

$N$ 的數列

$a$，有

$Q$ 個操作包括：

• 將一個區間中數列上的數每個都加上
  $d_i$
• 查詢一個區間的總和

例如

$a=(1,15,3,7,4)$，

$Q=2$ 筆詢問為：
將

$[2,6)$ 加上

$3$ 則

$a=(1,18,6,10,7)$
詢問

$[2,4)$ 的值，則區間總和為

$24$

可採用前面提的"單點更新/區間查詢"線段樹，
欲更新區間內所有數，對每數都單點更新，但總複雜度為

$O(Q\cdot N{\log }_{2}N)$

同理，這樣寫也可以做到區間更新：

void update(node* u, int L, int R, int qL, int qR, int d) {
  if(R <= qL || qR <= L) return;
  if(R-L == 1) {
    u->sum += d; // 更新該單點
    return;
  }
  
  int M = (L+R) / 2;
  update(u->lc, L, M, qL, qR, d);
  update(u->rc, M, R, qL, qR, d);
  
  u->sum = u->lc->sum + u->rc->sum;
}

以

$a=(1,15,3,7,4)$ 為例將

$[2,6)$ 所有數加上

$3$：

可是複雜度仍然為

$O(Q\cdot N{\log }_{2}N)$

Lazy tag

顧名思義，就是懶

懶是工程師的美德

由於更新區間的總和同時也將其子節點一併更新，這麼勤快肯定會花不少時間
如果當前區間的數全都得更新，可先偷懶做個 tag 值表示下方的子孫節點還未更新上 tag，
等到真正需要查(遞迴)到其子孫節點，在將 tag 往下推給子節點，以完成更新

Node

節點保存該區間的解及 tag，以及左右子節點的位置

struct node {
  int sum, tag;
  node *lc, *rc;
  node() { sum = tag = 0; lc = rc = NULL; }
  void pull() { sum = lc->sum + rc->sum; }
  void push(int L, int R) {
    lc->tag += tag;
    rc->tag += tag;
    
    int M = (L+R) / 2;
    lc->sum += tag * (M-L);
    rc->sum += tag * (R-M);
    
    tag = 0;
  }
};

• pull() 將左右子區間的總和加起來
• push() 將該區間的 tag 給左右子區間，並完成子節點的更新

Update

void update(node* u, int L, int R, int qL, int qR, int d) {
  if(R <= qL || qR <= L) return;
  if(qL <= L && R <= qR) {
    u->sum += d * (R-L);
    u->tag += d;
    return;
  }
  
  u->push(L, R);
  
  int M = (L+R) / 2;
  update(u->lc, L, M, qL, qR, d);
  update(u->rc, M, R, qL, qR, d);
  
  u->pull();
}

以

$a=(1,15,3,7,4)$ 為例將

$[2,6)$ 所有數加上

$3$：

其中左上角的值代表 tag 值。

與沒有 lazy tag 的區間更新相比，走訪的區間少了許多

Query

int query(node* u, int L, int R, int qL, int qR) {
  if(R <= qL || qR <= L) return 0;
  if(qL <= L && R <= qR) return u->sum;
  u->push(L, R);
  
  int M = (L+R) / 2;
  return query(u->lc, L, M, qL, qR) + query(u->rc, M, R, qL, qR)
}

以前個樹為例，詢問區間

$[2,4)$ 的總和：

觀察到，在查詢過程中會將 tag 往下 push 給子區間

練習：

POJ 3468 A Simple Problem with Integers
CODEFORCES 52C Circular RMQ

---

Binary Indexed Tree

又叫做 Fenwick Tree

翻譯為二元索引樹，可看作是線段樹的特化版本

二進制

整數可由一些

$2$ 的冪

$\{2^x\mid x\ge 0\}$ 組成，且每種冪次可只用一次
例如

$7=1+2+4$，二進制表示為

$111=001+010+100$
每個數字可由這種方式唯一的表示。換句話說，兩個不同數字就得用不同方式表現

也就是說用

$(001,010,100)$ 表達成

$111$ 也沒問題
那麼用

$111,(001,010)$ 表達同一件事也可以

$\text{lowbit}(x)$

$\text{lowbit}(x)$ 指的是

$x$ 用二進制表達時最低位的

$1$ 表示的

$2$ 的冪

$x=7$ 以二進制表達：

$\text{lowbit}(111)=001$

$x=6$ 以二進制表達：

$\text{lowbit}(110)=010$

$x=4$ 以二進制表達：

$\text{lowbit}(100)=100$

練習：

證明二補數系統下運算 x&-x 是

$x$ 的 lowbit

設

$y=x+\text{lowbit}(x)$ 證明

$y-\text{lowbit}(y)+1\le x-\text{lowbit}(x)+1$

單點更新/區間查詢

有了以上的基礎，可以回到正題了

給定長度

$N$ 的數列

$a$，有

$Q$ 個操作包括：

• 將數列上的一個數加上
  $d_i$
• 查詢一個區間的總和

若只有查詢操作，透過前綴和

$S$ 做

$S(R)-S(L-1)$ 能得

$[L,R]$ 區間和
但還得考慮更新操作，所以普通的前綴和是不行的

每次單點更新就得重新計算前綴和，複雜度會過高

根據前面基礎，用 for(; x >= 1; x-=lowbit(x)) sum += BIT[x] 求得

$[1,x]$ 區間和
例如

$x=7$ 那麼 sum 會得到 BIT[7] + BIT[6] + BIT[4]
其實就是把

$[1,7]$ 區間和表達成

$111,001,010$
兩者結合就是：BIT[

$111$] + BIT[

$111-001$] + BIT[

$111-001-010$]

而其中 BIT[x] 就能構造為

$[x-\text{lowbit}(x)+1,x]$ 的總和

$\sum _{i=x-\text{lowbit}(x)+1}^x{a}_i$
例如

$[1,7]$ 的總和就是

$\sum _{i=1}^4{a}_i+\sum _{i=5}^6{a}_i+\sum _{i=7}^7{a}_i=\sum _{i=1}^7{a}_i$

BIT 這種奇特區間定義能表示成一棵樹，例如

$[1,8]$ 的樹：

(觀察可知，這棵樹是把線段樹的右子樹通通移除的結果)

而若要更新數列的數，也要把包含此數的區間一併更新
例如更新位於位置

$x$ 的數，則

$[x-\text{lowbit}(x)+1,x]$ 要更新

$y=x+\text{lowbit}(x),[y-\text{lowbit}(y)+1,y]$ 也會包含

$x$ 位置，也得更新，依此類推

Update

單點更新

void update(int p, int d)
  { for(; p <= N; p+=p&-p) BIT[p] += d; }

複雜度為

$O(\log N)$，由於每次 lowbit 會至少進 1 位

Query

求前綴和

int pre(int p) {
  int sum = 0;
  for(; p >= 1; p-=p&-p) sum += BIT[p];  
  return sum;
}

複雜度為

$O(\log N)$，因為每次會去掉一個 bit

練習：
CODEFORCES 356A Knight Tournament
CODEFORCES 459D Pashmak and Parmida's problem
CODEFORCES 1042D Petya and Array
TIOJ 1175 Longest Increasing Subsequence
TIOJ 1080 A.逆序數對

區間更新/單點查詢

給定長度

$N$ 的數列

$a$，有

$Q$ 個操作包括：

• 將一個區間中數列上的數每個都加上
  $d_i$
• 查詢一個位置的值

應用差分(Difference)技巧令

$b_i=a_i-a_{i-1}$ 且

$b_1=a_1$
且透過

$b$ 建立 Binary Indexed Tree

Update

則若是將所有數

$a_i$ 加上

$d$，其中

$i\in [L,R]$
那麼

$b_{R+1}$ 與

$b_L$ 會變成：

$$\{\begin{array}{ll}{a}_{R+1}-(a_R+d)& =b_{R+1}-d\\ (a_L+d)-a_{L-1}& =b_L+d\end{array}$$
也就是說

$b_{R+1}$ 增加了

$-d$ 以及

$b_L$ 增加

$d$
而其餘的

$b_i\mid i\in [L+1,R]$ 都未增加任何值，因為差分定義讓

$d$ 相消了

則利用兩次單點更新

void update(int p, int d)
  { for(; p <= N; p+=p&-p) BIT[p] += d; }

做 update(L, d) 及 update(R+1, -d) 就能完成區間更新了

Query

根據差分定義推得

$a_i=\sum _{j=1}^i{b}_j$，所以可利用區間查詢

int pre(int p) {
  int sum = 0;
  for(; p >= 1; p-=p&-p) sum += BIT[p];  
  return sum;
}

做 pre(i) 能單點查詢

$a_i$ 的值

區間更新/區間查詢

給定長度

$N$ 的數列

$a$，有

$Q$ 個操作包括：

• 將一個區間中數列上的數每個都加上
  $d_i$
• 查詢一個區間的總和

根據差分定義有

$a_i=\sum _{j=1}^i{b}_j$
能推得

$a_1+a_2=b_1+(b_1+b_2)=2\cdot b_1+b_2$
能推得

$a_1+a_2+a_3=2\cdot b_1+b_2+(b_1+b_2+b_3)=3\cdot b_1+2\cdot b_2+b_3$
依此類推得

$\sum _{i=1}^x{a}_i=\sum _{i=1}^x(x-i+1)\cdot b_i=(x+1)\cdot \sum _{i=1}^x{b}_i-\sum _{i=1}^{x}i\cdot b_i$

於是，再多維護一個以數列

$\{i\cdot b_i{\}}_{i=1}^N$ 建立的 Binary Indexed Tree 就能求前綴和了