leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0315.cpp (820B)

0 class SegmentTree { 1 const int n; 2 vector<int> t = vector<int>(2 * n); 3 4 public: 5 SegmentTree(int n) : n(n) {} 6 7 int sum(int l, int r) const { 8 int res = 0; 9 10 for (l += n, r += n; l < r; l /= 2, r /= 2) { 11 if (l & 1) res += t[l++]; 12 if (r & 1) res += t[--r]; 13 } 14 15 return res; 16 } 17 18 void update(int p) { 19 for (t[p += n]++; p > 1; p /= 2) 20 t[p / 2] = t[p] + t[p ^ 1]; 21 } 22 }; 23 24 class Solution { 25 public: 26 vector<int> countSmaller(const vector<int> &nums) const { 27 const int n = size(nums); 28 SegmentTree seg(20001); 29 30 vector<int> res(n); 31 for (int i = n - 1; i >= 0; i--) { 32 seg.update(nums[i] + 10000); 33 res[i] = seg.sum(0, nums[i] + 10000); 34 } 35 36 return res; 37 } 38 };