????樹狀數(shù)組和線段數(shù)組最然非常方便，但維護(hù)的信息必須滿足信息合并特性（如區(qū)間可加，可減），如果不滿足此特性則不能使用樹狀數(shù)組和線段樹。分快算法可以維護(hù)一些線段樹維護(hù)不了的東西，分塊算法就是優(yōu)化過后的暴力。分塊是一個(gè)很暴力的算法，它可以完成幾乎所有區(qū)間更新和查詢的問題，但效率相對(duì)于線段樹等數(shù)據(jù)結(jié)構(gòu)要差一些。

????分塊算法是將數(shù)據(jù)分成若干個(gè)塊，維護(hù)塊內(nèi)信息，使得塊內(nèi)的查詢時(shí)O(1) 的時(shí)間，而總的詢問就可以看作若干個(gè)塊詢問的總和。

????分塊算法將長度為 n 的序列分成若干塊，每一塊有 k 個(gè)元素，最后一塊可能少于 k 個(gè)元素。為了使時(shí)間復(fù)雜度均攤，通常將塊的大小設(shè)為 k = n^(1/2), 用 pos[i] 表示第 i 個(gè)位置所屬的塊。對(duì)于每個(gè)塊都進(jìn)行信息維護(hù)。

1. 預(yù)處理

2. 區(qū)間修改

3. 區(qū)間查詢