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

• 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;
}
}
``````

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