C++ using binary index tree, segment tree and binary search tree


  • 1
    T

    For all the three methods, what we need to do is to find an efficient way to count the smaller numbers to the right of current number. In the naive method, each count takes O(N), while with tree structure, we can do this in O(logN).

    Binary search tree:

    class Solution {
    private: 
        struct Node // define tree node
        {
            int val; // val: current value; 
            int small; // small: number of smaller value than current value; 
            int self; // self: number of current value
            Node* left,*right; // left and right subtree pointers
            Node(int v):val(v),small(0),self(1),left(NULL),right(NULL){}
        };
    
        int BST(Node* root,int val)
        {
            // if node value is val, return the number of nodes in left subtree
            if(root->val==val) 
            {
                root->self++;
                return root->small;
            }
            // if node value is less than val, return sum of the number of nodes in left subtree and the searching result in right subtree
            else if(root->val<val)
            {
                // if right subtree is empty, add new node with value val
                if(root->right==NULL)
                {
                    root->right = new Node(val);
                    return root->small + root->self;
                }
                else return root->small + root->self + BST(root->right,val);
            }
            // if node value is larger than val, return the searching result in left subtree
            else
            {
                root->small++; // update the number of nodes in left subtree
                if(root->left==NULL) // if left subtree is empty, add new node with val
                {
                    root->left = new Node(val);
                    return 0;
                }
                else return BST(root->left,val);
            }
        }
    
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> result;
            if(nums.size()==0) return result;
            result = vector<int>(nums.size(),0);
            Node* root = new Node(nums[nums.size()-1]);
            for(int i=nums.size()-2;i>=0;i--) 
                result[i] = BST(root,nums[i]);
            return result;
        }
    };
    

    Binary indexed tree
    we need to create the binary indexed tree based on the sorted array, then we can count the number of elements that are smaller than current value. At each time, we first count the number of smaller values and then update current value to BIT, so only the smaller value to the left of current value (in original unsorted array) are counted.

    class Solution {
    private: 
        // update binary indexed tree, use a flatten array 'tree' to represent tree structure 
        void update(vector<int>& tree,int i,int val)
        {
            while(i<tree.size())
            {
                tree[i] += val;
                i += (-i&i); // calculate next index by adding right most set digit
            }
        }
        // count the number of smaller value to the right
        int count(vector<int>& tree,int i)
        {
            int sum = 0;
            while(i>0)
            {
                sum += tree[i];
                i -= (-i&i); // calculate next index by subtracting the right most set digit
            }
            return sum;
        }
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> result;
            if(nums.size()==0) return result;
            result = vector<int>(nums.size(),0);
            // copy nums and sort the copy version in ascending order
            vector<int> sorted_nums = nums;
            sort(sorted_nums.begin(),sorted_nums.end());
            // use a hash table to store the index of each distinct value in the sorted array
            unordered_map<int,int> hash;
            for(int i=0;i<sorted_nums.size();i++) hash[sorted_nums[i]] = i;
            // binary indexed tree container
            vector<int> tree = vector<int>(nums.size()+1,0);
            // we start from the right most element in nums
            for(int i=nums.size()-1;i>=0;i--)
            {
                // in each iteration, the 'count' function will count the total number of values that are samller than current number, but the values to the left of current number have not been added to BIT, so only the smaller values to the right of current number are counted
                result[i] = count(tree,hash[nums[i]]);
                // update the number of current value in BIT
                update(tree,hash[nums[i]]+1,1);
            }
            return result;
        }
    }
    

    Segment tree
    the idea in segment tree is pretty similar to binary indexed tree approach, basically what makes it different is the way we perform update and count with segment tree

    class Solution {
    private:
        // define tree node
        struct Node
        {
            int count; // number of value within the range of current node
            int ptr1,ptr2; // left and right boundary of current range
            Node* left,*right; // left and right subtree pointers
            Node(int c,int p1,int p2):count(c),ptr1(p1),ptr2(p2),left(NULL),right(NULL){}
        };
        // create segment tree
        Node* createST(int left,int right)
        {
            if(left==right) return new Node(0,left,right);
            int middle = (left+right)/2;
            Node* root = new Node(0,left,right);
            root->left = createST(left,middle);
            root->right = createST(middle+1,right);
            return root;
        }
        // update the number of values in segment tree
        void update(Node* root,int i,int val)
        {
            if(root==NULL) return;
            if(i>=root->ptr1 && i<=root->ptr2)
            {
                root->count += val;
                update(root->left,i,val);
                update(root->right,i,val);
            }
        }
        // count the number of smaller values to the right of current value
        int count(Node* root,int left,int right)
        {
            if(root==NULL) return 0;
            else if(root->ptr1>=left && root->ptr2<=right) return root->count;
            else if(root->ptr1>right || root->ptr2<left) return 0;
            else return count(root->left,left,right)+count(root->right,left,right);
        }
    
    public:
        vector<int> countSmaller(vector<int>& nums) {
            if(nums.size()==0) return vector<int>();
            vector<int> result = vector<int>(nums.size(),0);
            vector<int> sorted_nums = nums;
            sort(sorted_nums.begin(),sorted_nums.end());
            unordered_map<int,int> hash;
            for(int i=0;i<sorted_nums.size();i++) hash[sorted_nums[i]] = i;
            Node* root = createST(0,nums.size()-1);
            for(int i=nums.size()-1;i>=0;i--)
            {
                result[i] = count(root,0,hash[nums[i]]-1);
                update(root,hash[nums[i]],1);
            }
            return result;
        }
    }
    

Log in to reply
 

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