線段樹(1)

Introduction to Competitive Programming
2/17

• 介紹線段樹
• 單點加值
• 區間查詢

線段樹是用來處理區間問題的一種資料結構
這堂課先講單點加值和區間查詢
區間加值下堂課會講

結構

線段樹的結構大概會長這樣：

我們會用陣列表示一顆線段樹
假設總共有\(n\)個數字
我們會用開以\(4n\)為長度的陣列
樹高為\(logn\)

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

當前節點\(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\)

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

第\(5\)個節點表示區間\([3,4]\)的最大值為\(11\)
第\(3\)個節點表示區間\([5,8]\)的最大值為\(43\)

建樹

可以發現葉節點的區間長度皆為1，以區間長度等於1為結束遞迴的條件

#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()為更新答案的函式
對於不同的答案他會長的些微不一樣
以區間求最大值而言：

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

區間查詢

給你一個區間\([sl,sr]\)，你要如何快速找到這區間內的最大值

可以分成三種case去做：

1. 當前區間\([l,r]\)在\([sl,sr]\)裏面，可以直接回傳這個區間的答案

上圖\([l,r]\)在\([sl,sr]\)裏面，直接回傳\(75\)

2. 左邊區間有跟\([sl,sr]\)交集到，有就往左遞迴

上面兩種case的左區間都有跟\([sl,sr]\)交集到，要往左遞迴

3. 右邊區間有跟\([sl,sr]\)交集到，有就往右遞迴

上面兩種case的右區間都有跟\([sl,sr]\)交集到，要往右遞迴

注意第2和第3的case是獨立的，以下情況2,3都會成立，左右兩邊都要遞迴：

查詢\([2,7]\)這個區間的最大值

[0,8]左右兩個子區間都有跟[2,7]交集到
先往左遞迴

[0,4]左右兩個子區間都有跟[2,7]交集到
先往左遞迴

[0,2]只有右邊子區間有跟[2,7]交集到
往右遞迴

找到[2,2]，[2,2]這個區間在[2,7]內，回傳這個區間的最大值

回到[0,4]，因為右區間[3,4]有跟[2,7]交集到，往右遞迴
找到[3,4]這個區間在[2,7]內，回傳這個區間的最大值

回到[0,8]，因為右區間[5,8]有跟[2,7]交集到，往右遞迴

[5,8]左右兩個子區間都有跟[2,7]交集到，先往左遞迴
然後找到[5,6]在[2,7]這個區間內，回傳這個區間的最大值

回到[5,8]，因為右區間[7,8]有跟[2,7]交集到，往右遞迴

[7,8]，因為左區間[7,7]有跟[2,7]交集到，往左遞迴
因為[7,7]在[2,7]內，回傳這個區間的答案

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

實作查詢：

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

首先先從跟節點遞迴找到[1,1]區間的節點

更改這個節點的值

由下往上更新經過的點的最大值

由下往上更新經過的點的最大值

由下往上更新經過的點的最大值

由下往上更新經過的點的最大值

更新完畢

實作單點更新

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)\)

線段樹完整程式碼：

#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\)

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

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

像是區間[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]的總和

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

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

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

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

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

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

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

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

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

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

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

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

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

更新完畢

休息一下，等等有一堆例題講解！

例題：正負交替

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

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

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

ans是指每個區間的答案

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

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

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

把每個節點的資訊包成struct

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

總和：

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

最大前綴：

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

最大後綴：

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

區間連續最大和：

\[ 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在哪裡

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

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

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

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

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

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

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

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

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

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

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

來實作吧：
homework link