數列分塊概要

• 2021 年 3 月 1 日
• 筆記

分塊簡介

分塊是對數列進行操作的一種（在線毒瘤暴力卡常）數據結構，把數列分塊維護。主要處理區間問題

數列操作（L,R）：

找最值，求和，求大於、小於K元素個數等

分塊操作

一個對於[l，r]的操作，對於區間內完整的塊，我們直接維護整個塊的資訊；對於兩側不完整的塊，直接暴力。

        1.判斷要操作或是查詢的區間是否在一個塊內
        2.若在一個塊內，暴力操作或查詢
        3.若不在一個塊內，將除了最左邊和最右邊這兩個塊外其餘的塊進行整體的操作，即直接對塊打上修改標記之類的
        4.單獨暴力處理最左邊的塊和最右邊的塊

————引用自YuWenjue的部落格

分塊大小

數列長度為n時，一般為sqrt(n)

時間複雜度分析

初始化O(n),單次操作O(sqrt(n))

例題

見黃學長的部落格
將持續更新做題記錄