You are viewing a single comment's thread. Return to all comments →
class binary_index_tree { public: binary_index_tree(size_t size): sum_(size + 1) {} void put(int n) { while (n < sum_.size()) { sum_[n]++; n += n & (-n); } } int get(int n) { int total = 0; while (n > 0) { total += sum_[n]; n -= n&(-n); } return total; } private: vector<int> sum_; }; long long insertionSort(const vector<int>& arr) { long long count = 0, total = 0; binary_index_tree btree(1e7+10); for (int n : arr) { int less = btree.get(n); count += total - less; total++; btree.put(n); } return count; }
Seems like cookies are disabled on this browser, please enable them to open this website
Insertion Sort Advanced Analysis
You are viewing a single comment's thread. Return to all comments →