GeeksforGeeks: Segment Tree | Set 1 (Sum of given range), Segment Tree | Set 2 (Range Minimum Query), Binary Indexed Tree

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);
    
}