才剛剛開始/youl

• 線段樹
  • 最基礎的線段樹
    • 例1-洛谷P6492-STEP
      • 維護資訊
      • 合并資訊
    • 練習題1
  • 解決前綴最大值類問題-“樓房重建”型線段樹
    • 樓房重建
    • 練習題2
  • 李超線段樹
    • 練習題3

線段樹

最基礎的線段樹

首先是板子，維護最簡單的資訊以及懶標記的使用和下推（當然還有下推順序）

對于最一般的線段樹題（常規的維護序列資訊）只要會 pushup 和 pushdown（后者僅僅在有懶標記的時候需要）就能使用線段樹

pushup 即將節點 \(i\) 的左右兒子資訊合并成同等規模的 \(i\) 的資訊，例如區間最大值的 pushup 即為 \(maxval(i)=\max(maxval(lson),maxval(rson))\)

上面的板子的 pushup 和 pushdown 是最簡單的一類
做線段樹題需要三個要素

1. 線段樹節點上維護什么資訊
2. 如何將兩個區間的資訊合并成一個區間的資訊
3. 如果有懶標記，如何下推懶標記

用一道比較簡單的例題來體會上面的流程

例1-洛谷P6492-STEP

維護全域最長的形如 LRLRLR 的子段長（即，不包含 LL 或者 RR 的最長子段）
考慮如果我們知道了 \([L,mid]\) 和 \([mid+1,R]\) 的資訊，如何推出區間 \([L,R]\) 的資訊，也就是 \([L,R]\) 的答案（最長子段）是怎么產生的
顯然，\([L,R]\) 的最長子段只有 \(3\) 種情況

1. 完全來源于 \([L,mid]\)
2. 完全來源于 \([mid+1,R]\)
3. 跨過 \(mid\) 的一段，也就是由 \([L,mid]\) 的一段后綴和 \([mid+1,R]\) 的一段前綴拼成

所以，為了得到 \([L,R]\) 的答案
我們需要以下資訊：

1. \([L,mid]\) 的答案和 \([mid+1,R]\) 的答案（\(ans_{[L,mid]}\) 和 \(ans_{[mid+1,R]}\)）
2. \([L,mid]\) 的最長合法后綴和 \([mid+1,R]\) 的最長合法前綴（\(suf_{[L,mid]}\) 和 \(pre_{[mid+1,R]}\)）

那么是不是 \(ans_{[L,R]}=\max(ans_{[L,mid]},ans_{[mid+1,R]},suf_{[L,mid]}+pre_{[mid+1,R]})\) 呢
不完全是，因為 \(suf_{[L,mid]}+pre_{[mid+1,R]}\) 可能是 RLRL \(+\) LRLR 這樣的，雖然本身都是合法的，但是不能拼在一起
所以還要額外記錄 \([L,mid]\) 的最右邊字符以及 \([mid+1,R]\) 的最左邊字符，二者相異才能后綴拼前綴

三要素因為本題是單點修改變成了二要素

維護資訊

線段樹節點上維護該區間的最長合法子段長(\(ans_i\))、最長合法前綴(\(pre_i\))、最長合法后綴(\(suf_i\))、最左邊字符(\(lt_i\))、最右邊字符(\(rt_i\))、區間長度(\(len_i\))（區間長度是為了合并 \(pre_i\) 和 \(suf_i\)）

合并資訊

void pushup(int i)
{
    ans[i]=max(ans[ls],ans[rs]);
    lt[i]=lt[ls],rt[i]=rt[rs];
    pre[i]=pre[ls];
    if(rt[ls]!=lt[rs])
    {
        if(pre[ls]==len[ls]) pre[i]+=pre[rs];//前綴可能越過mid
        if(suf[rs]==len[rs]) suf[i]+=suf[ls];//后綴可能越過mid
        ans[i]=max(ans[i],suf[ls]+pre[rs]);
    }
    return ;
}

練習題1

洛谷P2894-Hotel-G
SDOI2010-序列操作

解決前綴最大值類問題-“樓房重建”型線段樹

參考了小粉兔的博客

樓房重建

單點修改，每次詢問 \(\sum\limits_{i=1}^n[\max\limits_{j<i}\{a_j\}<a_i]\) （多少個 \(i\) 是前綴 \(i\) 的嚴格最大值）

這種線段樹的 pushup 很不一樣，復雜度不再是常見的 \(O(1)\) 而是 \(O(\log n)\)

考慮區間 \([L,R]\) 的答案 \(res_{[L,R]}\)，顯然不能再 \(res_{[L,R]}=res_{[L,mid]}+res_{[mid+1,R]}\)，因為 \(res_{[mid+1,R]}\) 并沒有考慮 \([L,mid]\) 的影響，所以合并的時候最多只能繼承左半區間的答案，右半區間需要在考慮 \([L,mid]\) 的最大值對其的影響下重新計算

于是定義函式 calc(i,pre)，作用為計算節點 \(i\) 代表的區間在值 \(pre\) 的影響下的答案

記 \(cnt_i\) 表示節點 \(i\) 的右子樹的答案 （即區間 \([L,R]\) 在考慮 \([L,mid]\) 對右半區間的影響時右半區間的答案）

int calc(int L,int R,int i,int pre)//這里的L,R僅僅起到標識葉節點的作用
{
    if(L==R) return mx[i]>pre;
    int mid=L+R>>1;
    if(mx[ls]<=pre) return 0+calc(mid+1,R,rs,pre);//pre比左半區間的最大值還要大，那么左半區間不可能有任何貢獻
    else return calc(L,mid,ls,pre)+cnt[i];//否則pre對右半區間的影響不如左半區間對右半區間的影響，右半區間答案不變，重新計算左半區間
}

0+calc(mid+1,R,rs,pre) 因為 \(pre\) 大于左半區間最大值，左半區間連最大值都無法做出貢獻，所以左半區間答案為 \(0\)

calc(L,mid,ls,re)+cnt[i] 對于右半區間，左半區間的限制嚴格強于 \(pre\) 的限制，所以右半區間直接取 cnt[i]，重新計算左半區間

所以 pushup 就自然的寫出來

void pushup(int L,int R,int i)
{
    mx[i]=max(mx[ls],mx[rs]);
    int mid=L+R>>1;
    cnt[i]=calc(mid+1,R,rs,mx[ls]);
    return ;
}

回答詢問就直接 return calc(1,N,1,0)

由于 pushup 復雜度是 \(O(\log n)\) 的，所以 "樓房重建" 型線段樹時間復雜度為 \(O(Q\log^2 n)\)

練習題2

Vijos某題目

為了防止Vijos突然暴斃把題面留這里（

給定一棵 \(n\) 個節點的樹，每個節點有 \(a_i,b_i\) 兩個權值，你需要支持兩種操作

1. 詢問，給出起點終點 \(s,t\)，你將從 \(s\) 走到 \(t\)，每到一個節點 \(x\) 你會把手上大于 \(a_x\) 的數字都扔掉，然后獲得 \(b_x\) ，問走完 \(s-t\) 之后你手上有多少個數
2. 修改節點 \(x\) 的 \(a_x\)

\(1\le n\le 4\times 10^4,1\le Q\le 6\times 10^4\)

李超線段樹

支持插入直線/查詢最大值的線段樹

每個節點保存該區間的“優勢直線”，以及一個標記，標記該節點有沒有“優勢直線”

超哥樹就每個節點標記一下是不是有直線，插入的時候遇到空節點直接塞進來，否則考慮和已有直線的關系

1. 完全碾壓
   因為直線都是單調的，所以如果發現在當前區間左右端點都滿足待插入直線都比已有直線更優的話，已有直線就沒什么用了

2. 完全被碾壓
   同上，如果在當前區間左右端點都滿足待插入直線比已有直線更劣的話待插入直線就沒什么用了

3. 相交于區間內某一點
   排除掉1 2兩種情況之后已有直線和待插入直線就一定會相交于區間內的一點，以中點為劃分點來判斷
   -- 交點在左邊
   這時候右半區間一定是碾壓的局面，有爭議的只有左半邊，所以判斷一下右半邊是誰碾壓誰，如果是待插入直線碾壓已有直線，那么該區間優勢直線就是待插入直線，然后把已有直線插入左半區間
   -- 交點在右邊
   同上，這時候左半區間一定是碾壓局面，判斷一下是否替換優勢直線，然后繼續插入到有爭議的區間內即可

查詢的時候取遞回程序訪問到的每一條直線在查詢點處的縱坐標的最值作為答案
（寫的時候想到區間查詢這種東西，但是直線都是單調的所以區間查詢就是在區間端點處單點查詢取最值即可）
但是還有一種情況是區間插入，也就是插入的是線段不是直線，這種情況下區間查詢就不能再像上面那樣轉成兩個單點查詢，即使直線是單調的，但是可能區間內部有比較強的線段，但是在端點處查不到的情況

此時最好使用標記永久化，插入線段的時候如果當前區間完全被線段所在區間包含，就計算插入線段在端點處的值進行更新

時間復雜度，全域插入 \(O(n\log n)\)，區間插入 \(O(n\log^2n)\)

練習題3

HEOI2013-Segment

JSOI2008-Blue Mary開公司

SDOI2016-游戲

標籤：其他

上一篇：10-交換排序：冒泡排序

下一篇：重建二叉數（java）