<style> .reveal .slides { text-align: left; font-size:35px; } </style> ## 線段樹(1) Introduction to Competitive Programming 2/17 ---- - 介紹線段樹 - 單點加值 - 區間查詢 --- 線段樹是用來處理區間問題的一種資料結構 這堂課先講單點加值和區間查詢 區間加值下堂課會講 ---- ## 結構 線段樹的結構大概會長這樣： <center> <img src="https://hackmd.io/_uploads/HJnJ139tp.png" width="700px"> </center> ---- <center> <img src="https://hackmd.io/_uploads/S1pC1n5t6.png" width="700px"> </center> 我們會用陣列表示一顆線段樹 假設總共有$n$個數字 我們會用開以$4n$為長度的陣列 樹高為$logn$ ---- <center> <img src="https://hackmd.io/_uploads/S1pC1n5t6.png" width="700px"> </center> 當前節點的index為$i$ 左子節點為$2i$ 右子節點為$2i+1$ ---- <center> <img src="https://hackmd.io/_uploads/rJMMUhcFp.png" width="700px"> </center> 當前節點$i$有區間$[l,r]$ 定義$mid=(l+r)/2$ 左節點的區間為$[l,mid]$ 右節點的區間為$[mid+1,r]$ ---- 以下我們用這題來講解線段樹 給一個長度為$n$的陣列$a$，有$q$個操作，分為以下2種： - $1$ $l$ $r$ 詢問$[l,r]$區間的最大值 - $2$ $x$ $v$ 把$a_x$設為$v$ $1 \le n,q \le 2*10^5$ ---- <center> <img src="https://hackmd.io/_uploads/BJTslp9KT.png" width="700px"> </center> 假設當前陣列是a = [ 1, 5, 16, 7, 11, 4, 43, 15, 3] 當前節點$i$有區間$[l,r]$ 代表的是區間$[l,r]$內的最大值 ---- <center> <img src="https://hackmd.io/_uploads/BJTslp9KT.png" width="700px"> </center> 第$5$個節點表示區間$[3,4]$的最大值為$11$ 第$3$個節點表示區間$[5,8]$的最大值為$43$ ---- ## 建樹 可以發現葉節點的區間長度皆為1，以區間長度等於1為結束遞迴的條件 ```cpp! #define cl(x) (x<<1) #define cr(x) (x<<1)+1 void build(int id,int l,int r){ if(l==r){ seg[id]=arr[l]; return ; } int mid=(l+r)>>1; build(cl(id),l,mid); build(cr(id),mid+1,r); pull(id); } ``` ---- pull()為更新答案的函式 對於不同的答案他會長的些微不一樣 以區間求最大值而言： ```cpp! void pull(int id){ seg[id]=max(seg[cl(id)],seg[cr(id)]); } ``` ---- ## 區間查詢 給你一個區間$[sl,sr]$，你要如何快速找到這區間內的最大值 可以分成三種case去做： ---- 1. 當前區間$[l,r]$在$[sl,sr]$裏面，可以直接回傳這個區間的答案 <center> <img src="https://hackmd.io/_uploads/H1_i0Smc6.png" width="650px"> </center> 上圖$[l,r]$在$[sl,sr]$裏面，直接回傳$75$ ---- 2. 左邊區間有跟$[sl,sr]$交集到，有就往左遞迴 <center> <img src="https://hackmd.io/_uploads/S1fACHm9T.png" width="650px"> </center> 上面兩種case的左區間都有跟$[sl,sr]$交集到，要往左遞迴 ---- 3. 右邊區間有跟$[sl,sr]$交集到，有就往右遞迴 <center> <img src="https://hackmd.io/_uploads/By7QyIQ9p.png" width="650px"> </center> 上面兩種case的右區間都有跟$[sl,sr]$交集到，要往右遞迴 ---- 注意第2和第3的case是獨立的，以下情況2,3都會成立，左右兩邊都要遞迴： <center> <img src="https://hackmd.io/_uploads/ry0LyU7c6.png" width="650px"> </center> ---- 查詢$[2,7]$這個區間的最大值 <center> <img src="https://hackmd.io/_uploads/B1cNS8jK6.png" width="900px"> </center> ---- [0,8]左右兩個子區間都有跟[2,7]交集到 先往左遞迴 <center> <img src="https://hackmd.io/_uploads/HyfuU8otp.png" width="900px"> </center> ---- [0,4]左右兩個子區間都有跟[2,7]交集到 先往左遞迴 <center> <img src="https://hackmd.io/_uploads/B1r8PIiF6.png" width="900px"> </center> ---- [0,2]只有右邊子區間有跟[2,7]交集到 往右遞迴 <center> <img src="https://hackmd.io/_uploads/rycsPLsYa.png" width="900px"> </center> ---- 找到[2,2]，[2,2]這個區間在[2,7]內，回傳這個區間的最大值 <center> <img src="https://hackmd.io/_uploads/HJSl_IjK6.png" width="900px"> </center> ---- 回到[0,4]，因為右區間[3,4]有跟[2,7]交集到，往右遞迴 找到[3,4]這個區間在[2,7]內，回傳這個區間的最大值 <center> <img src="https://hackmd.io/_uploads/ByCut8oYT.png" width="900px"> </center> ---- 回到[0,8]，因為右區間[5,8]有跟[2,7]交集到，往右遞迴 <center> <img src="https://hackmd.io/_uploads/rkOV5UjK6.png" width="900px"> </center> ---- [5,8]左右兩個子區間都有跟[2,7]交集到，先往左遞迴 然後找到[5,6]在[2,7]這個區間內，回傳這個區間的最大值 <center> <img src="https://hackmd.io/_uploads/S1eysUotp.png" width="900px"> </center> ---- 回到[5,8]，因為右區間[7,8]有跟[2,7]交集到，往右遞迴 <center> <img src="https://hackmd.io/_uploads/SJSjj8sFa.png" width="900px"> </center> ---- [7,8]，因為左區間[7,7]有跟[2,7]交集到，往左遞迴 因為[7,7]在[2,7]內，回傳這個區間的答案 <center> <img src="https://hackmd.io/_uploads/H1qM28iFp.png" width="900px"> </center> ---- 總共有[2,2],[3,4],[5,6],[7,7]這些區間 <center> <img src="https://hackmd.io/_uploads/H1qM28iFp.png" width="900px"> </center> ---- 實作查詢： ```cpp! int query(int id,int l,int r,int sl,int sr){ if(sl<=l&&r<=sr){//目前這個區間在查詢區間內 return seg[id]; } int mid=(l+r)>>1,res=0; if(sl<=mid){//左區間跟查詢區間有交集 res=max(res,query(cl(id),l,mid,sl,sr)); } if(mid<sr){//右區間跟查詢區間有交集 res=max(res,query(cr(id),mid+1,r,sl,sr)); } return res; } ``` 複雜度：$O(logn)$ ---- ### 單點修改 以剛剛那顆線段樹舉例 我們要修改區間[1,1]的值把5變成17 <center> <img src="https://hackmd.io/_uploads/BJTslp9KT.png" width="900px"> </center> ---- 首先先從跟節點遞迴找到[1,1]區間的節點 <center> <img src="https://hackmd.io/_uploads/H1nqzvsYT.png" width="900px"> </center> ---- 更改這個節點的值 <center> <img src="https://hackmd.io/_uploads/HyZZmPiKT.png" width="900px"> </center> ---- 由下往上更新經過的點的最大值 <center> <img src="https://hackmd.io/_uploads/B1PDXPjY6.png" width="900px"> </center> ---- 由下往上更新經過的點的最大值 <center> <img src="https://hackmd.io/_uploads/S1WAQPjKp.png" width="900px"> </center> ---- 由下往上更新經過的點的最大值 <center> <img src="https://hackmd.io/_uploads/rJnZVwjYp.png" width="900px"> </center> ---- 由下往上更新經過的點的最大值 <center> <img src="https://hackmd.io/_uploads/B1SLNwiYa.png" width="900px"> </center> ---- 更新完畢 <center> <img src="https://hackmd.io/_uploads/rJAuNwiF6.png" width="900px"> </center> ---- ### 實作單點更新 ```cpp! void update(int id,int l,int r,int x,int v){ if(l==r){//這時候l和r會等於x seg[id]=v; return ; } int mid=(l+r)>>1; if(x<=mid){ update(cl(id),l,mid,x,v); } if(mid<x){ update(cr(id),mid+1,r,x,v); } pull(id); } ``` 複雜度$O(logn)$ ---- 線段樹完整程式碼： ```cpp! #define cl(x) (x<<1) #define cr(x) (x<<1)+1 const int N; int seg[4*N]; void pull(int id){ seg[id]=max(seg[cl(id)],seg[cr(id)]) } void build(int id,int l,int r){ if(l==r){ seg[id]=arr[l]; return ; } int mid=(l+r)>>1; build(cl(id),l,mid); build(cr(id),mid+1,r); pull(id); } void update(int id,int l,int r,int x,int v){ if(l==r){ seg[id]=v; return ; } int mid=(l+r)>>1; if(x<=mid){ update(cl(id),l,mid,x,v); } if(mid<x){ update(cr(id),mid+1,r,x,v); } pull(id); } int query(int id,int l,int r,int sl,int sr){ if(sl<=l&&r<=sr){//目前這個區間在查詢區間內 return seg[id]; } int mid=(l+r)>>1,res=0; if(sl<=mid){//左區間跟查詢區間有交集 res=max(res,query(cl(id),l,mid,sl,sr)); } if(mid<sr){//右區間跟查詢區間有交集 res=max(res,query(cr(id),mid+1,r,sl,sr)); } return res; } ``` ---- ## 區間求總和 給一個長度為$n$的陣列$a$，有$q$個操作，分為以下2種： - $1$ $l$ $r$ 詢問$[l,r]$區間的總和 - $2$ $x$ $v$ 把$a_x$設為$v$ $1 \le n,q \le 2*10^5$ ---- 可以發現就只是區間求最大值換成區間求總和 可以建出區間求總和的線段樹 <center> <img src="https://hackmd.io/_uploads/r1wYqBf96.png" width="900px"> </center> ---- 不難發現對於一個大區間而言，大區間的總和為左右兩個小區間相加 <center> <img src="https://hackmd.io/_uploads/BJ5L-87q6.png" width="700px"> </center> 像是區間[3,4]的值等於[3,3]+[4,4] 區間[5,8]的值等於[5,6]+[7,8] ---- build函式會跟區間求最大值一模一樣，因為只有更新答案的pull函式會不一樣，以下是區間求總和的pull函式 ```cpp! void pull(int id){ seg[id]=seg[cl(id)]+seg[cr(id)]; } ``` ---- 先來講這題的區間查詢🐍 這裡查詢[4,7]的總和 <center> <img src="https://hackmd.io/_uploads/BJcwQLX5a.png" width="900px"> </center> ---- 先看[0,8]的左右兩個子區間有沒有跟[4,7]交集到 因為都有，所以先往左遞迴 <center> <img src="https://hackmd.io/_uploads/Skhjm8Qc6.png" width="900px"> </center> ---- 現在到了[0,4]，只有右邊有跟[4,7]交集到，往右邊遞迴 <center> <img src="https://hackmd.io/_uploads/BJvzEUm5p.png" width="900px"> </center> ---- 目前為[3,4]，只有右邊有跟[4,7]交集到，往右邊遞迴 <center> <img src="https://hackmd.io/_uploads/H1S8NU75T.png" width="900px"> </center> ---- 目前為[4,4]，因為這個區間被包含在[4,7]裡面，回傳這個區間的答案 <center> <img src="https://hackmd.io/_uploads/ByNRV8Qcp.png" width="900px"> </center> ---- 回到[0,8]，解決右邊的部分還沒解決的部分，所以現在在[5,8] 因為[5,8]的左右兩個子區間都有跟[4,7]交集到，先往左遞迴 <center> <img src="https://hackmd.io/_uploads/SJQWrIQqa.png" width="900px"> </center> ---- 因為[5,6]的被[4,7]包含，回傳這個區間的答案 <center> <img src="https://hackmd.io/_uploads/HJXtrLXqT.png" width="900px"> </center> ---- 回到[5,8]解決右邊還沒解決的部分，所以現在到[7,8] 因為[7,8]的左區間跟[4,7]交集，右邊沒有，所以往左遞迴 <center> <img src="https://hackmd.io/_uploads/B1EkIIX9T.png" width="900px"> </center> ---- 現在到[7,7]，因為[7,7]在[4,7]內，所以回傳這個區間的答案 <center> <img src="https://hackmd.io/_uploads/B1aGIIX9a.png" width="900px"> </center> ---- 總共有[4,4]、[5,6]、[7,7]這些區間 <center> <img src="https://hackmd.io/_uploads/B1aGIIX9a.png" width="900px"> </center> ---- 區間查詢code be like: ```cpp! int query(int id,int l,int r,int sl,int sr){ if(sl<=l&&r<=sr){ return seg[id]; } int mid=(l+r)>>1,res=0; if(sl<=mid){ res+=query(cl(id),l,mid,sl,sr);//回傳值相加 } if(mid<sr){ res+=query(cr(id),mid+1,r,sl,sr);//回傳值相加 } return res; } ``` ---- 單點加值的話 這裡假設要在第三個單點加值7，也就是[2,2]這個區間 一樣先透過遞迴找到[2,2]這個區間 <center> <img src="https://hackmd.io/_uploads/Sy05D8mc6.png" width="900px"> </center> ---- 因為是加上7，所以[2,2]這個區間變成16 <center> <img src="https://hackmd.io/_uploads/SJvZOL7q6.png" width="900px"> </center> ---- 所經過的節點也要由下往上更新 <center> <img src="https://hackmd.io/_uploads/B12POU7ca.png" width="900px"> </center> ---- 所經過的節點也要由下往上更新 <center> <img src="https://hackmd.io/_uploads/rkVfKU756.png" width="900px"> </center> ---- 更新完畢 <center> <img src="https://hackmd.io/_uploads/ByZLFLXqp.png" width="900px"> </center> --- ## 休息一下，等等有一堆例題講解！ --- ## 例題：[正負交替](https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/A) 給一個長度為$n$的陣列$a$，有$q$個操作，分為以下2種： - $1$ $x$ $v$ 把$a_x$設為$v$ - $2$ $l$ $r$ 詢問$a_l-a_{l+1}+a_{l+2}...\pm a_{r}$的總和 ---- 觀察到每次詢問的正和負都是交替的 而$l$的位置固定為正 因此可以用$l$所在位置的奇偶性來建樹 ---- - 建偶數位為正值、奇數位為負值的樹 - 建偶數位為負值、奇數位為正值的樹 根據不同的$l$再去判斷要用哪顆線段樹去query就好了 ---- ## 例題：[區間不同數字數量](https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/D) 給一個長度為$n$的陣列$a$，$q$筆操作，有以下兩種操作 - $1$ $l$ $r$ 詢問區間$[l,r]$內有幾種不同的數字 - $2$ $x$ $v$ 把$a_x$設為$v$ $1 \le n,q \le 10^5$ $1 \le a_i \le 40$ ---- $a_i$最多有四十種，對於每一種$a_i$開一棵線段樹 時間複雜度：$O(nlogn)$ 空間複雜度：40\*4\*100000\*4bytes ---- 或是可以開一顆線段樹，裡面存long long的數字 long long可以存 64個bit，每一種bit存不同數字 再用or去運算求答案 ---- ## 例題：[區間最大連續和](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A) 給一個長度為$n$的陣列$a$，有$q$個操作，分為以下2種： - $1$ $l$ $r$ 詢問$[l,r]$的區間最大連續和 - $2$ $x$ $v$ 把$a_x$設為$v$ $1 \le n,q \le 2*10^5$ ---- 線段樹的核心觀念在於如何把小區間的答案合併到大區間 可以取下面兩塊小區間的答案轉移到大區間上 <center> <img src="https://hackmd.io/_uploads/HklaiFjYp.png" width="800px"> </center> ans是指每個區間的答案 ---- 如果大區間的最大連續和橫跨兩個區間並且為答案 <center> <img src="https://hackmd.io/_uploads/Hy4ITtsYT.png" width="900px"> </center> 需要下面兩塊的最大前綴和最大後綴相加 ---- 對於每一塊可以存當前總和、最大前綴、最大後綴和、當前區間內的區間連續最大和 <center> <img src="https://hackmd.io/_uploads/SJRjCYoKa.png" width="900px"> </center> ---- 把每個節點的資訊包成struct ```cpp! struct node{ int ans;//這個區間的答案 int sum;//這個區間的總和 int suf;//suffix 最大後綴 int pre;//prefix 最大前綴 }seg[4*N]; ``` ---- 總和： <center> <img src="https://hackmd.io/_uploads/ByImWqiYT.png" width="800px"> </center> $seg[id].sum=seg[cl(id)].sum+seg[cr(id)].sum$ ---- 最大前綴： <center> <img src="https://hackmd.io/_uploads/r1e4Q9sKT.png" width="800px"> </center> $$ seg[id].pre=max \begin{cases} seg[cl(id)].pre \\ seg[cl(id)].sum+seg[cr(id)].pre \end{cases} $$ ---- 最大後綴： <center> <img src="https://hackmd.io/_uploads/B1bNNqoKT.png" width="800px"> </center> $$ seg[id].suf=max \begin{cases} seg[cr(id)].suf \\ seg[cr(id)].sum+seg[cl(id)].suf \end{cases} $$ ---- 區間連續最大和： <center> <img src="https://hackmd.io/_uploads/B1vMS9iYT.png" width="700px"> </center> $$ seg[id].ans=max \begin{cases} seg[cl(id)].ans \\ seg[cr(id)].ans \\ seg[cl(id)].suf+seg[cr(id)].pre \end{cases} $$ ---- 因此會這樣更新： ```cpp! struct node{ int sum,pre,suf,ans;//總和、最大前綴、最大後綴、當前區間答案 }seg[4*N]; void pull(int id){ int l=cl(id),r=cr(id);//左右兩個子區間的index seg[id].sum=seg[l].sum+seg[r].sum; seg[id].pre=max(seg[l].pre,seg[l].sum+seg[r].pre); seg[id].suf=max(seg[r].suf,seg[r].sum+seg[l].suf); seg[id].ans=max({seg[l].ans,seg[r].ans,seg[l].suf+seg[r].pre}); } ``` --- ## 線段樹上二分搜 由於線段樹上每個大區間都會二分成兩個小區間 因此可以做一些二分搜之類的操作 ---- ## 例題：[第k個1](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/B) 長度為$n$的陣列$a$內只有0和1兩種數字，$q$筆操作 分為以下兩種： - $1$ $k$ 詢問陣列從左往右數來第$k$個1在哪個index - $2$ $x$ 把$a_x$的1變0或是0變1 $1 \le n,q \le 10^5$ ---- 假設陣列為a=[0,1,1,1,0,1,1,0] 可以以建區間總和的線段樹來做 這裡假設要查第四個1在哪裡 <center> <img src="https://hackmd.io/_uploads/B13x5CiF6.png" width="700px"> </center> ---- 左區間有三個1 右區間兩個1 往右邊遞迴找右邊的第一個1 <center> <img src="https://hackmd.io/_uploads/Byk6qCiF6.png" width="700px"> </center> ---- 左區間有一個1 右區間一個1 往左邊遞迴找左邊的第一個1 <center> <img src="https://hackmd.io/_uploads/Bk--n0sK6.png" width="700px"> </center> ---- 左區間有零個1 右區間一個1 往右邊遞迴找右邊的第一個1 <center> <img src="https://hackmd.io/_uploads/B1aBhAiK6.png" width="700px"> </center> ---- 找到了，回傳這個區間的$l$或$r$ <center> <img src="https://hackmd.io/_uploads/rkBu3CiKa.png" width="700px"> </center> ---- ## 例題：[至少大於K的第一個元素](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C) 給一個長度為$n$的陣列$a$，$q$筆操作，有以下兩種操作 - $1$ $k$ 詢問陣列從左往右數來第一個大於$k$的數字的index - $2$ $x$ $v$ 把$a_x$設為$v$ $1 \le n,q \le 10^5$ ---- 跟上一題概念一樣只是換成區間求最大的線段樹 ---- 能往左區間走就往左，否則往右 直到走到最下面，並回傳這個位置的$l$或$r$ <center> <img src="https://hackmd.io/_uploads/BJagik3tp.png" width="900px"> </center> 上圖為$k=8$的例子 --- 來實作吧： [homework link](https://vjudge.net/contest/603687)