Hello!
本篇延續了上一篇的內容。
本篇主要是參考 ( 抄襲 ) 這個大神的筆記。
假如看到內容有錯誤的話，再麻煩跟我說一聲了~
線段樹 ( Segment Tree )
線段樹建構
單點修改
區間查詢
例題 — Leetcode 307 （ 單點修改，區間查詢 ）
懶人標記：建構線段樹
懶人標記：區間修改
懶人標記：區間查詢
懶人標記：例題 — zeroJudge d799
動態開點
動態開點：例題 — Leetcode 715
多維線段樹
多維線段樹：例題 — leetcode 308
線段樹建構
假設我們現在建立線段樹的目的是為了求取區間最大值。
用一個陣列來表示線段樹，假如原陣列的長度為 n，則線段樹的陣列最多需要 4 * n 個元素，證明可看這篇!
segment_tree[0] 代表根節點。
假設我們目前在線段樹， index == i 的節點。
e.g. segment_tree[i]
則該節點的左子節點會是 i * 2 + 1，右子節點會是 i * 2 + 2
假如 left == right，表示目前該線段樹的節點只有一個，可以直接從原本的 input 陣列取值。
假若 left != right ， 則該線段樹的節點代表的區間裡，元素多於一。該區間的值可從兩個子節點拿取。
void build_segment_tree(int left, int right, int vertex,
vector<int> &segment_tree,
vector<int> &input) {
if(left == right) {
segment_tree[vertex] = input[left];
return;
} int mid = (left + right) / 2; build_segment_tree(left, mid, vertex * 2 + 1,
segment_tree, input);
build_segment_tree(mid + 1, right, vertex * 2 + 2,
segment_tree, input);
segment_tree[vertex] = max(segment_tree[vertex * 2 + 1],
segment_tree[vertex * 2 + 2]);
}
單點修改
利用二分搜尋，找出需要被修改的節點，是在線段樹中的哪一個元素。修改完後，該節點的所有祖先節點都要被更新。
void modifyOnePoint(int l, int r, int pos, int vertex, int value,
vector<int> &segment_tree) {
if(l == r) {
segment_tree[vertex] = value;
return;
} // 二分搜，找出需要被更改的節點，處於線段樹中的哪個位置
int mid = (l + r) / 2;
if(pos <= mid) {
modifyOnePoint(l, mid, pos, vertex, value,
segment_tree);
} else {
modifyOnePoint(mid + 1, r, pos, vertex, value,
segment_tree);
} // 更新所有祖先節點
segment_tree[vertex] = max(segment_tree[vertex * 2 + 1],
segment_tree[vertex * 2 + 2]);
}
區間查詢
vertex : 線段樹的節點
nowL : segment[vertex] 所代表的左邊界
nowR : segment[vertex] 所代表的右邊界
lookUpL : 希望查找的區間的左邊界
lookUpR : 希望查找的區間的右邊界
假如有完全符合的區間，則直接返回。
假如沒有完全符合，則用二分搜去查區間的所在位置。
假如欲查找的區間橫跨多個線段樹上的區間，則把欲查找的區間分成兩段，各自在線段樹上進行查找。
int lookUpInterval(int nowL, int nowR, int vertex,
int lookUpL, int lookUpR,
vector<int> &segment_tree) { // 假如有完全符合的區間，則直接返回。
if(nowL == lookUpL && nowR == lookUpR) {
return segment_tree[vertex];
} int mid = (nowL + nowR) / 2;// 假如沒有完全符合，則用二分搜去查區間的所在位置。
if(lookUpR <= mid) {
return lookUpInterval(nowL, mid, vertex * 2 + 1,
lookUpL, lookUpR, segment_tree);
} else if(lookUpL > mid) {
return lookUpInterval(mid + 1, nowR, vertex * 2 + 2,
lookUpL, lookUpR, segment_tree);
} else {
// 假如欲查找的區間橫跨多個線段樹上的區間，則把欲查找的區間分成兩段，各自在線段樹上進行查找。
int result = lookUpInterval(nowL, mid, vertex * 2 + 1,
lookUpL, mid, segment_tree);
result = max(result, lookUpInterval(mid + 1, nowR, vertex * 2 + 2,
mid + 1, lookUpR,
segment_tree));
return result;
}
return 0;
}
例題 — Leetcode 307 ( 單點修改，區間查詢 )
Update : 單點修改
sumRange : 區間查詢
class NumArray {
private:
vector<int> segment_tree;
int input_size = 0;
void build_segment_tree(int l, int r, int vertex, vector<int> &nums) {
if(l == r) {
segment_tree[vertex] = nums[l];
return;
}
int mid = (l + r) / 2;
build_segment_tree(l, mid, vertex * 2 + 1, nums);
build_segment_tree(mid + 1, r, vertex * 2 + 2, nums);
segment_tree[vertex] = segment_tree[vertex * 2 + 1] + \
segment_tree[vertex * 2 + 2];
}
void modifyOnePoint(int l, int r, int vertex, int pos, int val) {
if(l == r) {
segment_tree[vertex] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid) {
modifyOnePoint(l, mid, vertex * 2 + 1, pos, val);
} else {
modifyOnePoint(mid + 1, r, vertex * 2 + 2, pos, val);
}
segment_tree[vertex] = segment_tree[vertex * 2 + 1] + \
segment_tree[vertex * 2 + 2];
}
int lookUpInterval(int nowl, int nowr, int vertex,
int lookUpL, int lookUpR) {
if(nowl == lookUpL && nowr == lookUpR) {
return segment_tree[vertex];
}
int mid = (nowl + nowr) / 2;
if(lookUpR <= mid) {
return lookUpInterval(nowl, mid, vertex * 2 + 1,
lookUpL, lookUpR);
} else if(lookUpL > mid) {
return lookUpInterval(mid + 1, nowr, vertex * 2 + 2,
lookUpL, lookUpR);
} else {
int res = lookUpInterval(nowl, mid, vertex * 2 + 1,
lookUpL, mid);
res += lookUpInterval(mid + 1, nowr, vertex * 2 + 2,
mid + 1, lookUpR);
return res;
}
return 0;
}
public:
NumArray(vector<int>& nums) {
input_size = nums.size();
segment_tree = vector<int>(4 * nums.size());
build_segment_tree(0, nums.size() - 1, 0, nums);
}
void update(int index, int val) {
modifyOnePoint(0, input_size - 1, 0, index, val);
}
int sumRange(int left, int right) {
return lookUpInterval(0, input_size - 1, 0,
left, right);
}
};懶人標記：建構線段樹
在這裡，我們假設線段樹的節點是紀錄該區間的 "和"。
可以看到節點 struct Node 裡面多了一個 lazyTag。
typedef struct Node Node;
struct Node {
unsigned long long val;
unsigned long long lazyTag;
};using namespace std;void build_segment_tree(unsigned long long nowL, unsigned long long nowR, unsigned long long vertex,
vector<Node> &segment_tree, vector<unsigned long long> &input) {
if(nowL == nowR) {
segment_tree[vertex].val = input[nowL];
return;
} unsigned long long nowM = (nowL + nowR) / 2;
build_segment_tree(nowL, nowM, vertex * 2 + 1,
segment_tree, input); build_segment_tree(nowM + 1, nowR, vertex * 2 + 2,
segment_tree, input); segment_tree[vertex].val = segment_tree[vertex * 2 + 1].val + segment_tree[vertex * 2 + 2].val;
}
懶人標記：區間修改
使用的技巧常被稱為懶人標記， lazy tag, lazy propagation。
我猜是因為懶人標記會由父母節點開始往子節點傳播，所以才會被稱為 lazy propagation 吧。
void modify(unsigned long long nowL, unsigned long long nowR, unsigned long long modifyL, unsigned long long modifyR,
unsigned long long vertex, unsigned long long val,
vector<Node> &segment_tree) { // 在每次修改前，先把該節點的懶人標記更新到真正的值
if(segment_tree[vertex].lazyTag != 0) {
segment_tree[vertex].val += (nowR - nowL + 1) * segment_tree[vertex].lazyTag; // 記得要將懶人標記傳播給子節點 ( 假如存在子節點的話 )
if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += segment_tree[vertex].lazyTag; segment_tree[vertex * 2 + 2].lazyTag += segment_tree[vertex].lazyTag;
} segment_tree[vertex].lazyTag = 0;
}
// 假如區間完全符合，則直接進行修改
if(nowL == modifyL && nowR == modifyR) {
segment_tree[vertex].val += (modifyR - modifyL + 1) * val; // 記得要將懶人標記傳遞給子節點 ( 假如存在子節點的話 )
if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += val;
segment_tree[vertex * 2 + 2].lazyTag += val;
}
return;
} // 假如區間不完全符合，則二分搜區間
unsigned long long nowM = (nowL + nowR) / 2;
if(modifyR <= nowM) {
modify(nowL, nowM, modifyL, modifyR, vertex * 2 + 1, val,
segment_tree);
} else if(modifyL > nowM) {
modify(nowM + 1, nowR, modifyL, modifyR, vertex * 2 + 2, val,
segment_tree);
} else {
modify(nowL, nowM, modifyL, nowM, vertex * 2 + 1, val,
segment_tree); modify(nowM + 1, nowR, nowM + 1, modifyR, vertex * 2 + 2, val,
segment_tree);
} // 這裡要記得把懶人標記的值也補上去
segment_tree[vertex].val = segment_tree[vertex * 2 + 1].val + segment_tree[vertex * 2 + 1].lazyTag * (nowM - nowL + 1);
segment_tree[vertex].val += segment_tree[vertex * 2 + 2].val + segment_tree[vertex * 2 + 2].lazyTag * (nowR - (nowM + 1) + 1);}
懶人標記：區間查詢
unsigned long long lookUp(unsigned long long nowL, unsigned long long nowR,
unsigned long long lookUpL, unsigned long long lookUpR, unsigned long long vertex,
vector<Node> &segment_tree) { // 在每次修改前，先把該節點的懶人標記更新到真正的值
if(segment_tree[vertex].lazyTag != 0) {
segment_tree[vertex].val += (nowR - nowL + 1) * segment_tree[vertex].lazyTag; // 記得要將懶人標記傳播給子節點 ( 假如存在子節點的話 )
if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += segment_tree[vertex].lazyTag; segment_tree[vertex * 2 + 2].lazyTag += segment_tree[vertex].lazyTag;
} // fix segment_tree[vertex].lazyTag = 0;
} // 假如區間完全符合，則直接回傳值
if(nowL == lookUpL && nowR == lookUpR) {
return segment_tree[vertex].val;
} // 假如區間不完全符合，則二分搜區間
unsigned long long nowM = (nowL + nowR) / 2;
if(lookUpR <= nowM) {
return lookUp(nowL, nowM, lookUpL, lookUpR, vertex * 2 + 1,
segment_tree);
} else if(lookUpL > nowM) {
return lookUp(nowM + 1, nowR, lookUpL, lookUpR, vertex * 2 + 2,
segment_tree);
}
unsigned long long res = lookUp(nowL, nowM, lookUpL, nowM, vertex * 2 + 1,
segment_tree); res += lookUp(nowM + 1, nowR, nowM + 1, lookUpR, vertex * 2 + 2,
segment_tree); return res;
}
懶人標記：例題 zeroJudge d799
#include <iostream>
#include <vector>
#include <cstring>typedef struct Node Node;
struct Node {
unsigned long long val;
unsigned long long lazyTag;
};using namespace std;void build_segment_tree(unsigned long long nowL, unsigned long long nowR, unsigned long long vertex,
vector<Node> &segment_tree, vector<unsigned long long> &input) {
if(nowL == nowR) {
segment_tree[vertex].val = input[nowL];
return;
} unsigned long long nowM = (nowL + nowR) / 2;
build_segment_tree(nowL, nowM, vertex * 2 + 1,
segment_tree, input); build_segment_tree(nowM + 1, nowR, vertex * 2 + 2,
segment_tree, input); segment_tree[vertex].val = segment_tree[vertex * 2 + 1].val + segment_tree[vertex * 2 + 2].val;
}void modify(unsigned long long nowL, unsigned long long nowR, unsigned long long modifyL, unsigned long long modifyR,
unsigned long long vertex, unsigned long long val,
vector<Node> &segment_tree) { if(segment_tree[vertex].lazyTag != 0) {
segment_tree[vertex].val += (nowR - nowL + 1) * segment_tree[vertex].lazyTag; if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += segment_tree[vertex].lazyTag; segment_tree[vertex * 2 + 2].lazyTag += segment_tree[vertex].lazyTag;
} // fix segment_tree[vertex].lazyTag = 0;
} if(nowL == modifyL && nowR == modifyR) {
segment_tree[vertex].val += (modifyR - modifyL + 1) * val; if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += val;
segment_tree[vertex * 2 + 2].lazyTag += val;
}
return;
} unsigned long long nowM = (nowL + nowR) / 2;
if(modifyR <= nowM) {
modify(nowL, nowM, modifyL, modifyR, vertex * 2 + 1, val,
segment_tree);
} else if(modifyL > nowM) {
modify(nowM + 1, nowR, modifyL, modifyR, vertex * 2 + 2, val,
segment_tree);
} else {
modify(nowL, nowM, modifyL, nowM, vertex * 2 + 1, val,
segment_tree); modify(nowM + 1, nowR, nowM + 1, modifyR, vertex * 2 + 2, val,
segment_tree);
} // 這裡要記得把懶人標記的值也補上去
segment_tree[vertex].val = segment_tree[vertex * 2 + 1].val + segment_tree[vertex * 2 + 1].lazyTag * (nowM - nowL + 1);
segment_tree[vertex].val += segment_tree[vertex * 2 + 2].val + segment_tree[vertex * 2 + 2].lazyTag * (nowR - (nowM + 1) + 1);
}unsigned long long lookUp(unsigned long long nowL, unsigned long long nowR,
unsigned long long lookUpL, unsigned long long lookUpR, unsigned long long vertex,
vector<Node> &segment_tree) { if(segment_tree[vertex].lazyTag != 0) {
segment_tree[vertex].val += (nowR - nowL + 1) * segment_tree[vertex].lazyTag; if(nowL != nowR) { // fix, prevent segment fault
segment_tree[vertex * 2 + 1].lazyTag += segment_tree[vertex].lazyTag; segment_tree[vertex * 2 + 2].lazyTag += segment_tree[vertex].lazyTag;
} // fix segment_tree[vertex].lazyTag = 0;
}if(nowL == lookUpL && nowR == lookUpR) {
return segment_tree[vertex].val;
} unsigned long long nowM = (nowL + nowR) / 2;
if(lookUpR <= nowM) {
return lookUp(nowL, nowM, lookUpL, lookUpR, vertex * 2 + 1,
segment_tree);
} else if(lookUpL > nowM) {
return lookUp(nowM + 1, nowR, lookUpL, lookUpR, vertex * 2 + 2,
segment_tree);
}
unsigned long long res = lookUp(nowL, nowM, lookUpL, nowM, vertex * 2 + 1,
segment_tree); res += lookUp(nowM + 1, nowR, nowM + 1, lookUpR, vertex * 2 + 2,
segment_tree); return res;
}int main(int argc, char *argv[]) { int input_len;
cin >> input_len;
vector<unsigned long long> input(input_len);
vector<Node> segment_tree = vector<Node>(6 * input_len);
for(int i = 0;i < segment_tree.size();i++) {
memset(&(segment_tree[i]), 0, sizeof(Node));
} for(int i = 0;i < input_len;i++) {
cin >> input[i];
} build_segment_tree(0, input.size() - 1, 0,
segment_tree, input); int num_of_op;
cin >> num_of_op; for(int i = 0;i < num_of_op;i++) {
int op;
cin >> op;
if(op == 1) {
unsigned long long left, right, val;
cin >> left;
cin >> right;
cin >> val; left--;
right--; modify(0, input.size() - 1, left, right, 0, val,
segment_tree);
} else if(op == 2) {
unsigned long long left, right;
cin >> left;
cin >> right;
left--;
right--; unsigned long long res = lookUp(0, input.size() - 1, left, right, 0,
segment_tree);
cout << res << endl;
}
} return 0;
}
動態開點
當區間的範圍相當大，但是總節點數還算可以接受的範圍的時候，就需要動態開點了，而不是在一開始就將範圍所需的值通通定義出來。
動態開點：例題 — Leetcode 715
在這一題可以看到，值的範圍是 0 ~ 1000000000 ， 這直接開出一個大小為 10⁹ 個元素的陣列，肯定是會耗費大量的記憶體。
可以觀察到， “addRange, queryRange” 的總數量為 10⁴ ，所以使用的總結點數不會到 10⁹ 這麼的多。
其實操作跟一般的線段樹差不多，只差在節點只有在需要的時候，再用 newNode 將節點建構出來。
typedef struct Node Node;
struct Node {
int val;
int lazyTag;
bool isLazy;
struct Node *left;
struct Node *right;
};int timer = 0;class RangeModule {
private:
vector<Node> ns = vector<Node>(700000);
int timer = 0;
Node *newNode() {
return &ns[timer++];
}
void modify(int nowL, int nowR, int modifyL, int modifyR, int val, Node *nowN) {
if(nowN->isLazy) {
nowN->val = (nowR - nowL + 1) * nowN->lazyTag;
if(nowL != nowR) {
if(!nowN->left) {
nowN->left = newNode();
}
if(!nowN->right) {
nowN->right = newNode();
}
nowN->left->isLazy = true;
nowN->left->lazyTag = nowN->lazyTag;
nowN->right->isLazy = true;
nowN->right->lazyTag = nowN->lazyTag;
}
nowN->isLazy = false;
nowN->lazyTag = 0;
}
if(nowL == modifyL && nowR == modifyR) {
nowN->val = (nowR - nowL + 1) * val;
if(nowL != nowR) {
if(!nowN->left) {
nowN->left = newNode();
}
if(!nowN->right) {
nowN->right = newNode();
}
nowN->left->isLazy = true;
nowN->left->lazyTag = val;
nowN->right->isLazy = true;
nowN->right->lazyTag = val;
}
return;
}
int nowM = (nowL + nowR) / 2;
if(modifyR <= nowM) {
if(!nowN->left) {
nowN->left = newNode();
}
modify(nowL, nowM, modifyL, modifyR, val, nowN->left);
} else if(modifyL > nowM) {
if(!nowN->right) {
nowN->right = newNode();
}
modify(nowM + 1, nowR, modifyL, modifyR, val, nowN->right);
} else {
if(!nowN->left) {
nowN->left = newNode();
}
if(!nowN->right) {
nowN->right = newNode();
}
modify(nowL, nowM, modifyL, nowM, val, nowN->left);
modify(nowM + 1, nowR, nowM + 1, modifyR, val, nowN->right);
}
int temp = 0;
if(nowN->left) {
if(nowN->left->isLazy) {
temp += nowN->left->lazyTag * (nowM - nowL + 1);
} else {
temp += nowN->left->val;
}
}
if(nowN->right) {
if(nowN->right->isLazy) {
temp += nowN->right->lazyTag * (nowR - (nowM + 1) + 1);
} else {
temp += nowN->right->val;
}
}
nowN->val = temp;
}
int lookUp(int nowL, int nowR, int lookUpL, int lookUpR, Node *nowN) {
if(nowN->isLazy) {
nowN->val = (nowR - nowL + 1) * nowN->lazyTag;
if(nowL != nowR) {
if(!nowN->left) {
nowN->left = newNode();
}
if(!nowN->right) {
nowN->right = newNode();
}
nowN->left->isLazy = true;
nowN->left->lazyTag = nowN->lazyTag;
nowN->right->isLazy = true;
nowN->right->lazyTag = nowN->lazyTag;
}
nowN->isLazy = false;
nowN->lazyTag = 0;
}
if(nowL == lookUpL && nowR == lookUpR) {
return nowN->val;
}
int nowM = (nowL + nowR) / 2;
if(lookUpR <= nowM) {
if(!nowN->left) {
nowN->left = newNode();
}
return lookUp(nowL, nowM, lookUpL, lookUpR, nowN->left);
} else if(lookUpL > nowM) {
if(!nowN->right) {
nowN->right = newNode();
}
return lookUp(nowM + 1, nowR, lookUpL, lookUpR, nowN->right);
}
if(!nowN->left) {
nowN->left = newNode();
}
if(!nowN->right) {
nowN->right = newNode();
}
int temp = 0;
temp += lookUp(nowL, nowM, lookUpL, nowM, nowN->left);
temp += lookUp(nowM + 1, nowR, nowM + 1, lookUpR, nowN->right);
return temp;
}
public:
Node *segment_tree;
RangeModule() {
segment_tree = newNode();
}
void addRange(int left, int right) {
modify(0, 1000000001, left - 1, right - 2, 1, segment_tree);
// printf("timer : %d\n", timer);
}
bool queryRange(int left, int right) {
int val = lookUp(0, 1000000001, left - 1, right - 2, segment_tree);
// half inverval!
if(val == (right - left)) {
return true;
}
return false;
}
void removeRange(int left, int right) {
modify(0, 1000000001, left - 1, right - 2, 0, segment_tree);
}
};/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule* obj = new RangeModule();
* obj->addRange(left,right);
* bool param_2 = obj->queryRange(left,right);
* obj->removeRange(left,right);
*/
多維線段樹
有時候線段樹可能不只有一個維度。當想要有多維的線段樹的時候，其實就是在每一個線段樹的節點裡面，再塞一個線段樹。
多維線段樹例題 — leetcode 308
class NumMatrix {
private:
vector<vector<int>> segTree;
int wide, height;
void build_tree3(int nowRowL, int nowRowR, int nowColL, int nowColR, int row, int col) {
if(nowColL == nowColR) {
segTree[row][col] = segTree[row * 2 + 1][col] + segTree[row * 2 + 2][col];
return;
}
int nowColM = (nowColL + nowColR) / 2;
build_tree3(nowRowL, nowRowL, nowColL, nowColM, row, col * 2 + 1);
build_tree3(nowRowL, nowRowL, nowColM + 1, nowColR, row, col * 2 + 2);
segTree[row][col] = segTree[row][col * 2 + 1] + segTree[row][col * 2 + 2];
}
void build_tree2(int nowRowL, int nowRowR, int nowColL, int nowColR, int row, int col, vector<vector<int>> &matrix) {
if(nowColL == nowColR) {
segTree[row][col] = matrix[nowRowL][nowColL];
return;
}
int nowColM = (nowColL + nowColR) / 2;
build_tree2(nowRowL, nowRowR, nowColL, nowColM, row,
col * 2 + 1, matrix);
build_tree2(nowRowL, nowRowR, nowColM + 1, nowColR, row,
col * 2 + 2, matrix);
segTree[row][col] = segTree[row][col * 2 + 1] + segTree[row][col * 2 + 2];
}
void build_tree(int nowRowL, int nowRowR, int row,vector<vector<int>> &matrix) {
if(nowRowL == nowRowR) {
build_tree2(nowRowL, nowRowR, 0, matrix[0].size() - 1, row, 0,matrix);
return;
}
int nowRowM = (nowRowL + nowRowR) / 2;
build_tree(nowRowL, nowRowM, row * 2 + 1, matrix);
build_tree(nowRowM + 1, nowRowR, row * 2 + 2, matrix);
build_tree3(nowRowL, nowRowR, 0, height - 1, row, 0);
}
void modify3(int nowRowL, int nowRowR, int nowColL, int nowColR, int row, int col) {
if(nowColL == nowColR) {
segTree[row][col] = segTree[row * 2 + 1][col] + segTree[row * 2 + 2][col];
return;
}
int nowColM = (nowColL + nowColR) / 2;
modify3(nowRowL, nowRowR, nowColL, nowColM, row, col * 2 + 1);
modify3(nowRowL, nowRowR, nowColM + 1, nowColR, row, col * 2 + 2);
segTree[row][col] = segTree[row][col * 2 + 1] + segTree[row][col * 2 + 2];
}
void modify2(int nowRowL, int nowRowR, int nowColL, int nowColR, int row, int col, int posRow, int posCol, int val) {
if(nowColL == nowColR) {
segTree[row][col] = val;
return;
}
int nowColM = (nowColL + nowColR) / 2;
if(posCol <= nowColM) {
modify2(nowRowL, nowRowR, nowColL, nowColM, row, col * 2 + 1, posRow, posCol, val);
} else {
modify2(nowRowL, nowRowR, nowColM + 1, nowColR, row, col * 2 + 2, posRow, posCol, val);
}
segTree[row][col] = segTree[row][col * 2 + 1] + segTree[row][col * 2 + 2];
}
void modify(int nowRowL, int nowRowR, int row, int posRow, int posCol, int val) {
if(nowRowL == nowRowR) {
modify2(nowRowL, nowRowR, 0, height - 1, row, 0, posRow, posCol, val);
return;
}
int nowRowM = (nowRowL + nowRowR) / 2;
if(posRow <= nowRowM) {
modify(nowRowL, nowRowM, row * 2 + 1, posRow, posCol, val);
} else if(posRow > nowRowM) {
modify(nowRowM + 1, nowRowR, row * 2 + 2, posRow, posCol, val);
}
modify3(nowRowL, nowRowR, 0, height - 1, row, 0);
}
int lookUp2(int nowRowL, int nowRowR, int nowColL, int nowColR, int row1, int row2, int col1, int col2, int row, int col) {
if(nowColL == col1 && nowColR == col2) {
return segTree[row][col];
}
int nowColM = (nowColL + nowColR) / 2;
if(col2 <= nowColM) {
return lookUp2(nowRowL, nowRowR, nowColL, nowColM, row1, row2, col1, col2, row, col * 2 + 1);
} else if(col1 > nowColM) {
return lookUp2(nowRowL, nowRowR, nowColM + 1, nowColR, row1, row2, col1, col2, row, col * 2 + 2);
} else {
int res = 0;
res += lookUp2(nowRowL, nowRowR, nowColL, nowColM, row1, row2, col1, nowColM, row, col * 2 + 1);
res += lookUp2(nowRowL, nowRowR, nowColM + 1, nowColR, row1, row2, nowColM + 1, col2, row, col * 2 + 2);
return res;
}
return 0;
}
int lookUp(int nowRowL, int nowRowR, int row1, int row2, int col1, int col2, int row) {
if(nowRowL == row1 && nowRowR == row2) {
return lookUp2(nowRowL, nowRowR, 0, height - 1, row1, row2, col1, col2, row, 0);
}
int nowRowM = (nowRowL + nowRowR) / 2;
if(row2 <= nowRowM) {
return lookUp(nowRowL, nowRowM, row1, row2, col1, col2, row * 2 + 1);
} else if(row1 > nowRowM) {
return lookUp(nowRowM + 1, nowRowR, row1, row2, col1, col2, row * 2 + 2);
} else {
int res = 0;
res += lookUp(nowRowL, nowRowM, row1, nowRowM, col1, col2, row * 2 + 1);
res += lookUp(nowRowM + 1, nowRowR, nowRowM + 1, row2, col1, col2, row * 2 + 2);
return res;
}
return 0;
}
public:
NumMatrix(vector<vector<int>>& matrix) {
segTree = vector<vector<int>>(matrix.size() * 4, vector<int>(matrix[0].size() * 4));
wide = matrix.size();
height = matrix[0].size();
build_tree(0, matrix.size() - 1, 0, matrix);
}
void update(int row, int col, int val) {
modify(0, wide - 1, 0, row, col, val);
}
int sumRegion(int row1, int col1, int row2, int col2) {
return lookUp(0, wide - 1, row1, row2, col1, col2, 0);
}
};/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* obj->update(row,col,val);
* int param_2 = obj->sumRegion(row1,col1,row2,col2);
*/
Bye!
普通的線段樹支援了單點修改以及區間的查詢，假若想要支援區間修改的話，就要好好地使用懶人標記了。
假若範圍過大，難以一次就 malloc 足夠的空間地話，就需要使用動態開點的技巧，只有在有需要的時候，將節點 malloc 出來。
假若線段樹所需處理的資料超過一個維度，則需要在第一個維度的每個素裡，再塞一棵線段樹了。
終於學習到了一些線段樹的技巧，接下來就要學習 Binary Indexed Tree 了。
在某次面試時被考到 BIT ，而當時的我完全不知道這是什麼東西，所以理所當然被刷掉了 XD
希望下次面試時再碰到 BIT 的話，可以好好地答出來 QQ
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
