題目描述

處理一個長度為 $n$ 的數列，支持兩種操作：

• 區間加法；
• 單點查詢。

若使用暴力，時間複雜度會逹到 $O(n^2)$，無法通過 subtask 2，因此考慮使用分塊。

甚麼是分塊？

分块是將數組列分成若干個大小相近的塊，平衡時間複雜度。

如何分塊？

1. 將長度為 $n$ 的數組分成 $m$ 個塊，每個塊的大小為 $\frac{n}{m}$。
2. 對每個塊，使用一個「懶標記」（類似線段樹）記錄該塊內所有元素需要累加的值，以避免每次更新時都遍歷塊內所有元素。

分塊的最佳大小

塊的大小是分塊算法的關鍵，直接影響時間複雜度。下面將分析為甚麼選擇 $\sqrt{n}$ 作為塊大小最好：

設塊的大小為 $s$，則總塊數為 $m = \lceil\frac{n}{s}\rceil$。

對於區間操作，可以分成下列兩部分：

• 處理左右兩個的不完整塊，最多遍歷 $2s$ 個元素，時間複雜度是 $O(s)$。
• 處理中間的完整塊，最多遍歷 $m$ 個塊，因為只需更新懶標記，所以時間複雜度是 $O(m)$。

即單次操作的總時間複雜度為 $O(s + m) = O(s + \frac{n}{s})$。

設 $f(x) = s + \frac{n}{s}$。
根據均值不等式 $f(x) = s + \frac{n}{s} \ge 2 \sqrt{s \times \frac{n}{s}} = 2 \sqrt{n}$ ，當且僅當 $s = \sqrt{n}$ 時等號成立。

因此，當塊大小為 $\sqrt{n}$ 時，單次操作的時間複雜度最佳，為 $O(\sqrt{n})$。對於 $n$ 次操作，總時間複雜度為 $O(n\sqrt{n})$。