Hello!
最近開始看些資料結構與演算法的東西，驚覺自己的實力竟然比高中生還差勁。雖然已經從研究所畢業工作一段時間了，但我的實力仍舊停留在別人國，高中程度（甚至不如國，高中程度）。希望可以在工作之餘，盡量彌補一些知識了。
本篇主要是參考 ( 抄襲 ) 這個大神的筆記。
假如看到內容有錯誤的話，再麻煩跟我說一聲了~
前綴和
輸入一個長度為 n 的陣列，以及一個數字 q ，q 代表查詢的次數。
每次的查詢會需要輸入 k, r ，回傳 [k, r] 的區間和。
→ 區間查詢，不做任何修改
例題： LeetCode 303. Range Sum Query — Immutable
→ 區間查詢 ( 區間和 )
假如暴力解，也就是每次都從第 k 個元素加到第 r 個元素，此時會需要
O( nq ) 的時間複雜度。
但假若我們先整理出前綴和的話，就可以將 O( nq ) 優化成 O( q )。
class NumArray {
public: vector<int> prefixSum;
NumArray(vector<int>& nums) {
prefixSum = vector<int>(nums.size(), 0); int sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
prefixSum[i] = sum;
}
}
int sumRange(int i, int j) {
if(i == 0) {
return prefixSum[j];
}
return prefixSum[j] - prefixSum[i - 1]; }
};
差分序列
輸入一個長度為 n 的陣列，以及一個數字 q ，q 代表區間要被修改的次數。
每次的查詢會需要輸入 k, r, x，區間 [k, r] 會加上 x
在最後需要回傳這個陣列最後的值。
→ 區間修改，不做任何查詢 ( 或僅作一次的查詢 )
例題：370. Range Addition
→ 區間修改
假如說我們有一個陣列
int A[5] = {2, 3, 6, 7, 1};則 A 的差分序列 B 會是
int B[5] = {A[0], A[1] - A[0], A[2] - A[1], A[3] - A[2], A[4] - A[3]};
-->
int B[5] = {2, 1, 3, 1, -6};當我們想要對 [l, r] 區間做 +x 時，可以對 B[l] + x，對 B[r+1] -x
e.g. [1, 3] + 10
int B[5] = {2, 1 + 10, 3, 1, -6 - 10};
--> int B[5] = {2, 11, 3, 1, -16}最後我們可以依靠差分序列得出原本的陣列
int B[5] = {2, 11, 3, 1, -16}
--> int A[5] = {2, 13, 16, 17, 1}離散化
例如以前綴和的題目為例子，並且做一些變形。給訂一個區間：[1, 100000000000]， 該區間內的整數上會放置一個籃子。接下來會有 q 個輸入， 每個輸入會有兩個數字 k, p 。會在 k 這個整數的位子上，加上數字 p。
q 的範圍是 1 ~ 100000。
這邊可以看到，用原本的前綴和方法，會需要一個長度為 1000000000 的陣列
例題：印象中有解過，但忘記是哪題了 QQ
int A[100000000000] = { 0 };
void add (int k, p) {
A[k] += p;
}這邊可以看到 100000000000 ( Byte ) * 4 / 1024 / 1024 / 1024 = 372… GB
這表示想要做這件事，我們需要有 372 GB 的主記憶體 + swap 才行，這實在是太花錢了。
但我們注意到，輸入的數量最多是 100000，所以我們可以將輸入整理成長度為 100000 的陣列，這樣我們只需要 100000 ( Byte )* 4 / 1024 = 390 KB。
int A[100000000000] = { 0 };
A[0] = 100;
A[10] = 1000;
A[99999999999] = 10;
-->
int B[100000] = { 0 };
B[0] = 100;
B[1] = 1000;
B[2] = 10;前綴和與差分序列
前綴和可以在 O(n) 的處理後，在 O( 1 ) 時間拿到區間和，但沒辦法 O(1) 做區間修改
差分序列可以在 O( n ) 的處理後，在 O( 1 ) 時間做出區間修改，但沒辦法 O(1) 做區間和
分塊法
關於分塊法，這篇已經講得很好了，我覺得我沒辦法說的比這篇還要好，還要完整了 QQ。
在遇到區間的問題時，可以將一個陣列區分成不同的區塊，每一個區塊都為護著自己的解答。當我們查找的區間包含著某一個完整的區塊時，可以直接回傳該區塊的解答，而不用去遍尋區塊內的所有元素。
例題：d539: 區間 MAX
→ 區間查詢 ( 區間最大值 )
例題：d799: 區間求和
→ 區間查詢 ( 區間和 )，區間修改
例題：307. Range Sum Query — Mutable
→ 區間查詢，單點修改
例題：715. Range Module
→ 區間查詢，區間修改
這邊以例題：d539: 區間 MAX 為例， 把長度為 n 的陣列區分為一塊塊長度為 根號 n 的區塊。
如此一來可以達到 O(n * sqrt(n)) 的時間複雜度。但這樣還不夠快，在這一題會 TLE!!
希望能更快的話，需要繼續往下看 sparse table 了。使用 sparse table ， 可以達到 O(n * log n)。
#include <iostream>
#include <vector>
#include <cmath>using namespace std;int lookUp(vector<int> &input, vector<int> &block, int l, int r, int k) { int res = 0; for(int i = l;i <= r;) {
if(i % k == 0 && i + k <= r) {
res = max(res, block[i / k]);
i += k;
} else {
res = max(res, input[i]);
i++;
}
} return res;
}int main(int argc, char *argv[]) { string st;
cin >> st; int n = atoi(st.c_str());
vector<int> input;
for(int i = 0;i < n;i++) {
cin >> st;
input.push_back(atoi(st.c_str()));
} cin >> st;
n = atoi(st.c_str()); // length of single block
int k = sqrt(input.size()); // num of blocks
int nb = input.size() / k;
if(input.size() % k != 0) {
nb++;
} vector<int> block = vector<int>(nb, 0);
for(int i = 0;i < input.size();i++) {
block[i / k] = max(input[i], block[i / k]);
} for(int i = 0;i < n;i++) {
int a, b;
cin >> st;
a = atoi(st.c_str());
cin >> st;
b = atoi(st.c_str()); int left = min(a, b) - 1;
int right = max(a, b) - 1; int ans = lookUp(input, block, left, right, k);
cout << ans << endl;
} return 0;
}
Bye!
在這裡先暫時打住了，之後會再繼續學習 sparse table, segment tree, Binary Indexed Tree 等更厲害的內容！
Reference
- 區間問題概述 — 這篇太厲害了!
- Segment tree & Lazy Propagation
- 大神的線段樹筆記
- wikipedia : 線段樹
- 建國中學，演算法講義 : 線段樹詳解
- 資訊之芽算法班
- 資訊之芽
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree.pdf
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/segment_tree_2.pdf
https://www.csie.ntu.edu.tw/~sprout/algo2018/ppt_pdf/Segment_Tree_inclass.pdf
