Segment Tree | Set 1 (Sum of given range)
ref:
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
1维
void updateHelper(vector<int> &tree,int diff,int i,int start,int end,int index) {
if (i < start || i > end) return;
tree[index] += diff;
if (start != end) {
int mid = (start + end) / 2;
updateHelper(tree,diff,i,start,mid,index * 2 + 1);
updateHelper(tree,diff,i,mid + 1,end,index * 2 + 2);
}
}
void update(vector<int> &nums, vector<int> &tree,int i,int newValue) {
int diff = newValue - nums[i];
nums[i] = newValue;
updateHelper(tree,diff,i,0,nums.size() - 1,0);
}
int query(vector<int> &tree,int targetS, int targetE, int curS, int curE,int index) {
if (curS >= targetS && curE <= targetE) {
return tree[index];
}
if (curS > targetE || curE < targetS) {
return 0;
}
int mid = (curS + curE) / 2;
return query(tree,targetS,targetE,curS,mid,index * 2 + 1) + query(tree,targetS,targetE,mid + 1,curE,index * 2 + 2);
}
int query(vector<int> &nums,vector<int> &tree,int start,int end) {
return query(tree,start,end,0,nums.size() - 1,0);
}
int buildTree(vector<int> &nums,vector<int> &tree,int start,int end,int i) {
//cout << i << endl;
if (start == end) {
tree[i] = nums[start];
return tree[i];
}
int mid = (start + end) / 2;
tree[i] = buildTree(nums,tree,start,mid,2 * i + 1)
+ buildTree(nums,tree,mid + 1,end,2 * i + 2);
return tree[i];
}
void segmentTree(vector<int> &nums) {
vector<int> tree(1000,0);
buildTree(nums,tree,0,nums.size() - 1,0);
}
2维
2维的build tree单独搞不出来，最后只能用调用update，O( n^2 * lgn * lgn)
void updateY(vector<vector<int>> &tree,int y1,int cY1,int cY2,int x,int y,int diff) {
if (y1 > cY2 || y1 < cY1) return;
tree[x][y] += diff;
if (cY1 == cY2) return;
int mid = (cY1 + cY2) / 2;
updateY(tree,y1,cY1,mid,x,y * 2 + 1,diff);
updateY(tree,y1,mid + 1,cY2,x,y * 2 + 2,diff);
}
void updateX(vector<vector<int>> &tree,int x1,int y1,int cX1,int cY1,int cX2,int cY2,int x,int y,int diff) {
if (x1 > cX2 || x1 < cX1) return;
updateY(tree,y1,cY1,cY2,x,y,diff);
if (cX1 == cX2) return;
int mid = (cX1 + cX2) / 2;
updateX(tree,x1,y1,cX1,cY1,mid,cY2,2 * x + 1,y,diff);
updateX(tree,x1,y1,mid + 1,cY1,cX2,cY2, 2 * x + 2,y,diff);
}
int getYSum(vector<vector<int>> &tree,int y1,int y2,int cY1,int cY2,int x,int y) {
if (y1 <= cY1 && y2 >= cY2) {
return tree[x][y];
}
if (y1 > cY2 || y2 < cY1) return 0;
int mid = (cY1 + cY2) / 2;
return getYSum(tree,y1,y2,cY1,mid,x,y * 2 + 1) + getYSum(tree,y1,y2,mid + 1,cY2,x,y * 2 + 2);
}
int getXSum(vector<vector<int>> &tree,int x1,int y1,int x2,int y2,int cX1,int cY1,int cX2,int cY2,int x,int y) {
if (x1 <= cX1 && x2 >= cX2) {
return getYSum(tree,y1,y2,cY1,cY2,x,y);
}
if (x1 > cX2 || x2 < cX1) return 0;
int mid = (cX1 + cX2) / 2;
return getXSum(tree,x1,y1,x2,y2,cX1,cY1,mid,cY2,2 * x + 1,y) + getXSum(tree,x1,y1,x2,y2,mid + 1,cY1,cX2,cY2, 2 * x + 2,y);
}
void twoDSegmentTree(vector<vector<int>> &matrix) {
vector<vector<int>> tree(1000,vector<int>(1000,0));
int m = matrix.size(),n = matrix[0].size();
// build 2d segment tree
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
updateX(tree,i,j,0,0,m - 1,n - 1,0,0,matrix[i][j]);
}
}
}
------------------------------------------------------------------------------------
Segment Tree | Set 2 (Range Minimum Query)
ref:
http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
int updateHelper(vector<int> &tree,int newValue,int i,int start,int end,int index) {
if (i < start || i > end) return INT_MAX;
if (start == end) {
tree[index] = newValue;
return tree[index];
}
int mid = (start + end) / 2;
tree[index] = min(updateHelper(tree,newValue,i,start,mid,index * 2 + 1),
updateHelper(tree,newValue,i,mid + 1,end,index * 2 + 2));
return tree[index];
}
void update(vector<int> &nums, vector<int> &tree,int i,int newValue) {
nums[i] = newValue;
updateHelper(tree,newValue,i,0,nums.size() - 1,0);
}
int query(vector<int> &tree,int targetS, int targetE, int curS, int curE,int index) {
if (curS >= targetS && curE <= targetE) {
return tree[index];
}
if (curS > targetE || curE < targetS) {
return INT_MAX;
}
int mid = (curS + curE) / 2;
return min(query(tree,targetS,targetE,curS,mid,index * 2 + 1), query(tree,targetS,targetE,mid + 1,curE,index * 2 + 2));
}
int query(vector<int> &nums,vector<int> &tree,int start,int end) {
return query(tree,start,end,0,nums.size() - 1,0);
}
int buildTree(vector<int> &nums,vector<int> &tree,int start,int end,int i) {
if (start == end) {
tree[i] = nums[start];
return tree[i];
}
int mid = (start + end) / 2;
tree[i] = min(buildTree(nums,tree,start,mid,2 * i + 1),
buildTree(nums,tree,mid + 1,end,2 * i + 2));
return tree[i];
}
void segmentTree(vector<int> &nums) {
vector<int> tree(1000,0);
buildTree(nums,tree,0,nums.size() - 1,0);
}
-----------------------------------------------------------------
Binary Indexed Tree
ref:
http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
http://www.hawstein.com/posts/binary-indexed-trees.html
http://algorithmsandme.in/2015/02/binary-indexed-trees/
1维
void update(vector<int> &bit,int idx,int diff) {
while (idx < bit.size()) {
bit[idx] += diff;
idx += idx & (-idx);
}
}
int get(vector<int> &bit,int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & (-idx);
}
return sum;
}
vector<int> buildTree(vector<int> &nums) {
vector<int> bit(nums.size() + 1,0);
for (int i = 0; i < nums.size(); i++) {
update(bit,i + 1,nums[i]);
}
return bit;
}
void biTree(vector<int> &nums) {
vector<int> bit = buildTree(nums);
}
2维bit
#1 每个row的sum，再做一个bit，就成了2维的了
求[i][j]的值需要从[0][i] 到 [i][j]
#2 如果求[x1,y1]到[x2,y2]的矩阵的值，则要做一些矩阵减法
void update(vector<vector<int>> &bit, int row,int col,int diff) {
while (row < bit.size()) {
int idx = col;
while (idx < bit[0].size()) {
bit[row][idx] += diff;
idx += idx & (-idx);
}
row += row & (-row);
}
}
int read(vector<vector<int>> &bit, int row,int col) {
int sum = 0;
while (row > 0) {
int idx = col;
while (idx > 0) {
sum += bit[row][idx];
idx -= idx & (-idx);
}
row -= row & (-row);
}
return sum;
}
vector<vector<int>> buildBit(vector<vector<int>> &matrix) {
vector<vector<int>> bit(matrix.size() + 1,vector<int>(matrix[0].size() + 1,0));
for (int row = 0; row < matrix.size(); row++) {
for (int col = 0; col < matrix[0].size(); col++) {
update(bit,row + 1,col + 1,matrix[row][col]);
}
}
return bit;
}
void twoDBit(vector<vector<int> > &matrix) {
vector<vector<int>> bit = buildBit(matrix);
}
