C++ summary for the BIT Problem Set


  • 0
    F

    Range Sum Query

    Solution 1

    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            num.resize(nums.size() + 1);
            bit.resize(nums.size() + 1);
            for (int i = 0; i < nums.size(); ++i) {
                update(i, nums[i]);
            }
        }
        void update(int i, int val) {
            int diff = val - num[i + 1];
            for (int j = i + 1; j < num.size(); j += (j&-j)) {
                bit[j] += diff;
            }
            num[i + 1] = val;
        }
        int sumRange(int i, int j) {
            return getSum(j + 1) - getSum(i);
        }    
        int getSum(int i) {
            int res = 0;
            for (int j = i; j > 0; j -= (j&-j)) {
                res += bit[j];
            }
            return res;
        }
    
    private:
        vector<int> num;
        vector<int> bit;
    };
    

    Solution 2

     class NumArray {
        private:
            vector<int> _nums;
            vector<int> bit;
            
            int lower_bit(int i){
                return i&-i;
            }
            
            int query(int i){
                i++;
                int sum=0;
                while(i>0){
                    sum+=bit[i];
                    i-=lower_bit(i);
                }
                return sum;
            }
            
            void add(int i, int val){
                i++;
                while(i<bit.size()){
                    bit[i]+=val;
                    i+=lower_bit(i);
                }
            }
            
        public:
            NumArray(vector<int> &nums) : _nums(nums) {
                bit.resize(nums.size()+1);
                for(int i=0; i<nums.size(); i++){
                    add(i, nums[i]);
                }
            }
        
            void update(int i, int val) {
                if(val!=_nums[i]){
                    add(i, val-_nums[i]);
                    _nums[i]=val;
                }
            }
        
            int sumRange(int i, int j) {
                return query(j)-query(i-1);
            }
        };
    

    Range Sum Query 2D - Mutable

    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if (matrix.empty() || matrix[0].empty()) return;
            mat.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
            bit.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
            for (int i = 0; i < matrix.size(); ++i) {
                for (int j = 0; j < matrix[i].size(); ++j) {
                    update(i, j, matrix[i][j]);
                }
            }
        }
    
        void update(int row, int col, int val) {
            int diff = val - mat[row + 1][col + 1];
            for (int i = row + 1; i < mat.size(); i += i&-i) {
                for (int j = col + 1; j < mat[i].size(); j += j&-j) {
                    bit[i][j] += diff;
                }
            }
            mat[row + 1][col + 1] = val;
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            return getSum(row2 + 1, col2 + 1) - getSum(row1, col2 + 1) - getSum(row2 + 1, col1) + getSum(row1, col1);
        }
        
        int getSum(int row, int col) {
            int res = 0;
            for (int i = row; i > 0; i -= i&-i) {
                for (int j = col; j > 0; j -= j&-j) {
                    res += bit[i][j];
                }
            }
            return res;
        } 
        
    private:
        vector<vector<int>> mat;
        vector<vector<int>> bit;
    };
    

    Count of smaller numbers after itself

    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> t, res(nums.size());
            for (int i = nums.size() - 1; i >= 0; --i) {
                int left = 0, right = t.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (t[mid] >= nums[i]) right = mid;
                    else left = mid + 1;
                }
                res[i] = right;
                t.insert(t.begin() + right, nums[i]);
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.