owned this note changed 8 hours ago
Published Linked with GitHub

線段樹 1

Introduction to Competitive Programming
3/20


  • 線段樹是什麼?
  • 如何實現單點加值
  • 如何實現區間查詢

結構

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

我們會用陣列表示一顆線段樹
假設總共有 \(n\) 個數字
樹高為 \(\lceil \log n \rceil + 1\)
節點數為 \(2^{\lceil \log n \rceil + 1} - 1\)
我們可以把陣列大小開 \(4 * n\)
\(2^{\lceil \log n \rceil + 1} - 1 < 4 \times 2^{\log n}\)


Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

當前節點的index為\(i\)
左子節點為\(2i\)
右子節點為\(2i+1\)


Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

當前節點\(i\)有區間\([l,r]\)
定義\(mid=(l+r)/2\)
左節點的區間為\([l,mid]\)
右節點的區間為\([mid+1,r]\)


Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

如果一段區間的資訊可以透過兩個子區間的資訊來合併
就可以使用線段樹
每個節點存取一段區間的資訊
透過合併不同節點的資訊可以獲得任何一段區間的答案


簡單例題

給一個長度為\(n\)的陣列\(a\),有\(q\)個操作,分為以下2種:

  • \(1\) \(l\) \(r\) 詢問\([l,r]\)區間的最大值
  • \(2\) \(x\) \(v\)\(a_x\)設為\(v\)

\(1 \le n,q \le 2*10^5\)


Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

假設當前陣列是a = [ 1, 5, 16, 7, 11, 4, 43, 15, 3]
當前節點\(i\)有區間\([l,r]\)
代表的是區間\([l,r]\)內的最大值


建樹

可以發現葉節點的區間長度皆為1,以區間長度等於1為結束遞迴的條件
因為有 左閉右開 / 左閉右閉 許多版本 所以這邊只給程式碼概念

#define cl(x) (x << 1)    
#define cr(x) ((x << 1) | 1)
void build(int id,int l,int r){
    if ( 區間長度為1 ){
        info[id] = arr[l]; 
        return ;
    }
    int mid = (l+r) >> 1;
    build(cl(id), l, mid);
    build(cr(id), mid + 1, r);
    // 合併兩個區間
    info[id] = max(info[cl(id)], info[cr(id)]);
}

區間查詢

假設要查詢區間 [2, 6]
image
就是拿這三塊去merge


可以簡單分成 3 種情況

  • 當前區間被查詢區間包含
  • 當前區間和查詢區間不相交
  • 前兩種以外的情況(有相交)
    不相交的話當前區間資訊沒有意義
    包含的話不用繼續遞歸他的子節點
    其他情況要繼續遞歸
inline i32 cl(i32 x) { return x << 1; }
inline i32 cr(i32 x) { return (x << 1) | 1; }
int rangeQuery(i32 p, i32 l, i32 r, i32 x, i32 y) {
    if (l >= y || r <= x) return -inf; // 不相交 回傳極小值,對答案沒有貢獻
    if (l >= x && r <= y) return info[p]; // 包含
    i32 m = (l + r) >> 1;
    return max(rangeQuery(cl(p), l, m, x, y), rangeQuery(cr(p), m, r, x, y));
}

單點修改

如果要修改 [7] 綠色的部分都有可能被修改
image


我們先遞歸找到最底下長度為 1 那個要修改的點
修改那個點,然後往上合併更新他的父節點

inline i32 cl(i32 x) { return x << 1; }
inline i32 cr(i32 x) { return (x << 1) | 1; }
void modify(i32 p, i32 l, i32 r, i32 x, int v) {
    if (r - l == 1) { //
        info[p] = v;
        return;
    }
    i32 m = (l + r) >> 1;
    if (x < m) modify(cl(p), l, m, x, v);
    else modify(cr(p), m, r, x, v);
    info[p] = max(info[cl(p)], info[cr(p)]);
}

完整程式碼

左閉右開


區間求總和

給一個長度為\(n\)的陣列\(a\),有\(q\)個操作,分為以下2種:

  • \(1\) \(l\) \(r\) 詢問\([l,r]\)區間的總和
  • \(2\) \(x\) \(v\)\(a_x\)設為\(v\)

\(1 \le n,q \le 2*10^5\)


可以發現就只是區間求最大值換成區間求總和
可以建出區間求總和的線段樹

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

不難發現對於一個大區間而言,大區間的總和為左右兩個小區間相加

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

像是區間[3,4]的值等於[3,3]+[4,4]
區間[5,8]的值等於[5,6]+[7,8]


build函式會跟區間求最大值一模一樣,因為只有更新答案的pull函式會不一樣,以下是區間求總和的pull函式

void pull(int id){
    seg[id]=seg[cl(id)]+seg[cr(id)];
}

先來講這題的區間查詢🐍
這裡查詢[4,7]的總和

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

先看[0,8]的左右兩個子區間有沒有跟[4,7]交集到
因為都有,所以先往左遞迴

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

現在到了[0,4],只有右邊有跟[4,7]交集到,往右邊遞迴

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

目前為[3,4],只有右邊有跟[4,7]交集到,往右邊遞迴

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

目前為[4,4],因為這個區間被包含在[4,7]裡面,回傳這個區間的答案

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

回到[0,8],解決右邊的部分還沒解決的部分,所以現在在[5,8]
因為[5,8]的左右兩個子區間都有跟[4,7]交集到,先往左遞迴

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

因為[5,6]的被[4,7]包含,回傳這個區間的答案

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

回到[5,8]解決右邊還沒解決的部分,所以現在到[7,8]
因為[7,8]的左區間跟[4,7]交集,右邊沒有,所以往左遞迴

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

現在到[7,7],因為[7,7]在[4,7]內,所以回傳這個區間的答案

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

總共有[4,4]、[5,6]、[7,7]這些區間

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

區間查詢code be like:

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]這個區間

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

因為是加上7,所以[2,2]這個區間變成16

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

所經過的節點也要由下往上更新

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

所經過的節點也要由下往上更新

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

更新完畢

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

休息一下,等等有一堆例題講解!


例題:正負交替

給一個長度為\(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就好了


例題:區間不同數字數量

給一個長度為\(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去運算求答案


例題:區間最大連續和

給一個長度為\(n\)的陣列\(a\),有\(q\)個操作,分為以下2種:

  • \(1\) \(l\) \(r\) 詢問\([l,r]\)的區間最大連續和
  • \(2\) \(x\) \(v\)\(a_x\)設為\(v\)

\(1 \le n,q \le 2*10^5\)


線段樹的核心觀念在於如何把小區間的答案合併到大區間

可以取下面兩塊小區間的答案轉移到大區間上

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

ans是指每個區間的答案


如果大區間的最大連續和橫跨兩個區間並且為答案

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

需要下面兩塊的最大前綴和最大後綴相加


對於每一塊可以存當前總和、最大前綴、最大後綴和、當前區間內的區間連續最大和

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

把每個節點的資訊包成struct

struct node{
    int ans;//這個區間的答案
    int sum;//這個區間的總和
    int suf;//suffix 最大後綴
    int pre;//prefix 最大前綴
}seg[4*N];

總和:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

\(seg[id].sum=seg[cl(id)].sum+seg[cr(id)].sum\)


最大前綴:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

\[ seg[id].pre=max \begin{cases} seg[cl(id)].pre \\ seg[cl(id)].sum+seg[cr(id)].pre \end{cases} \]


最大後綴:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

\[ seg[id].suf=max \begin{cases} seg[cr(id)].suf \\ seg[cr(id)].sum+seg[cl(id)].suf \end{cases} \]


區間連續最大和:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

\[ seg[id].ans=max \begin{cases} seg[cl(id)].ans \\ seg[cr(id)].ans \\ seg[cl(id)].suf+seg[cr(id)].pre \end{cases} \]


因此會這樣更新:

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

長度為\(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在哪裡

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

左區間有三個1 右區間兩個1
往右邊遞迴找右邊的第一個1

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

左區間有一個1 右區間一個1
往左邊遞迴找左邊的第一個1

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

左區間有零個1 右區間一個1
往右邊遞迴找右邊的第一個1

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

找到了,回傳這個區間的\(l\)\(r\)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

例題:至少大於K的第一個元素

給一個長度為\(n\)的陣列\(a\)\(q\)筆操作,有以下兩種操作

  • \(1\) \(k\) 詢問陣列從左往右數來第一個大於\(k\)的數字的index
  • \(2\) \(x\) \(v\)\(a_x\)設為\(v\)

\(1 \le n,q \le 10^5\)


跟上一題概念一樣只是換成區間求最大的線段樹


能往左區間走就往左,否則往右
直到走到最下面,並回傳這個位置的\(l\)\(r\)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

上圖為\(k=8\)的例子


來實作吧:
homework link

Select a repo