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++) t[n + i] = nums[i];

7 for (int i = n - 1; i > 0; i--) t[i] = t[i * 2] + t[i * 2 + 1];

8 }

9

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

11 int res = 0;

12

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

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

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

16 }

17

18 return res;

19 }

20

21 void update(int p, int val) {

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

23 }

24 };