leetcode

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