leetcode

0 class SegmentTree {

1 const int n;

2 vector<int> t = vector<int>(2 * n);

3

4 public:

5 SegmentTree(const vector<int> nums) : n(size(nums)) {

6 for (int i = 0; i < n; i++)

7 t[n + i] = nums[i];

8 for (int i = n - 1; i > 0; i--)

9 t[i] = t[i * 2] + t[i * 2 + 1];

10 }

11

12 int sum(int l, int r) const {

13 int res = 0;

14

15 for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {

16 if (l & 1) res += t[l++];

17 if (r & 1) res += t[--r];

18 }

19

20 return res;

21 }

22

23 void update(int p, int val) {

24 for (t[p += n] = val; p > 1; p /= 2)

25 t[p / 2] = t[p] + t[p ^ 1];

26 }

27 };

28

29 class NumArray {

30 SegmentTree seg;

31

32 public:

33 NumArray(const vector<int> &nums) : seg(nums) {}

34 void update(int index, int val) { seg.update(index, val); }

35 int sumRange(int left, int right) const { return seg.sum(left, right); }

36 };