# [easy to understand with details] C++ implementation inspired from the Binary Index Tree

• My first implementation can't pass the case

``````[11, 11]
``````

After analyzing all the code, I know that the problem lays at the code to compute the places[] array.

when the numbers equal, I SHOULD set the number index different and the latter appearance should

corresponds to bigger index. So My original code can not satisfy this condition.

``````all the cases contain duplicate number
``````

HOW SHOULD I CHANGE MY CODE TO DEAL WITH THIS CASE?

Solution:

`````` result[i]=bit_sum(places[i]-1);
``````

calculate the sum to the places[i]-1 is the sum of the small numbers.

``````class Solution {
vector<int> bit;
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> result(nums.size(), 0);
bit.resize(nums.size()+1, 0);

//get the ordered-index-array
vector<int> sorted_nums(nums);
vector<int> places(nums.size(), 0);
sort(sorted_nums.begin(), sorted_nums.end());
for (int i = 0; i < nums.size(); ++i) {
places[i] = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
cout<<i<<"th places:"<<places[i]<<endl;
}

for(int i=places.size()-1; i>=0; i--){
result[i]=bit_sum(places[i]-1);
}

return result;
}

int bit_last(int i){
return i&-i;
}

i++;
while(i<bit.size()){
bit[i]+=val;
i=i+bit_last(i);
}
}

int bit_sum(int i){
i++;
int sum=0;
while(i>0){
sum+=bit[i];
i=i-bit_last(i);
}
return sum;
}
};

/*
5,2,6,1
2,1,3,0
from-end-to-start-traverse
insert(0)
get_sum(0)
insert(3)
get_sum(3)
insert(1)
get_sum(1)
insert(2)
get_sum(2)
*/``````

• ``````class Solution {
vector<int> bit;
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> sorted_nums(nums);
vector<int> dict(nums.size(), 0);
vector<int> result(nums.size(), 0);
bit.resize(nums.size()+1, 0);
/*** use-O(N)-space-to-get-the-order-number-array ***/
unordered_map<int, int> map;
sort(sorted_nums.begin(), sorted_nums.end());
for(int i=0; i<nums.size(); i++){
map[sorted_nums[i]]=i+1;
}
for(int i=0; i<nums.size(); i++){
dict[i]=map[nums[i]];
}
/*** use binary-index-tree-idea to query the result in O(NlogN) ***/
for(int i=dict.size()-1; i>=0; i--){
result[i]=bit_sum(dict[i]-1);
}
return result;
}

int last_bit(int i){
return i&-i;
}

i++;
while(i<bit.size()){
bit[i]+=val;
i+=last_bit(i);
}
}

int bit_sum(int i){
i++;
int sum=0;
while(i>0){
sum+=bit[i];
i-=last_bit(i);
}
return sum;
}
};``````

• ``````class Solution {
vector<int> bit;
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> sorted_nums(nums);
vector<int> dict(nums.size(), 0);
vector<int> result(nums.size(), 0);
bit.resize(nums.size() + 1, 0);

unordered_map<int, int> map;
sort(sorted_nums.begin(), sorted_nums.end());
for(int i = 0; i < nums.size(); i++) {
map[sorted_nums[i]] = i + 1;
}
for(int i = 0; i < nums.size(); i++) {
dict[i] = map[nums[i]];
}

for(int i = dict.size()-1; i >= 0; i--) {
result[i] = bit_sum(dict[i] - 1);
}

return result;
}

int last_bit(int i) {
return i & (-i);
}

void bit_add(int i, int val) {
i++;
while(i < bit.size()) {
bit[i] += val;
i += last_bit(i);
}
}

int bit_sum(int i) {
i++;
int sum = 0;
while(i > 0) {
sum += bit[i];
i -= last_bit(i);
}
return sum;
}
};``````

• ``````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 d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
res[i] = d;
t.insert(t.begin() + d, nums[i]);
}
return res;
}
};``````

• @fight.for.dream
use map instead of vector<int> could be more efficient because insert in map is o(log(n)) while in vector it is o(n)

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