leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0315.cpp (820B)

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