leetcode

0 class SegmentTree {

1 const int n;

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

3

4 void build(const vector<int>& nums, int idx, int left, int right) {

5 if (left == right) {

6 t[idx] = nums[left];

7 return;

8 }

9

10 const int mid = (left + right) / 2;

11 build(nums, idx * 2, left, mid);

12 build(nums, idx * 2 + 1, mid + 1, right);

13 t[idx] = t[idx * 2] + t[idx * 2 + 1];

14 }

15

16 int sum(int idx, int left, int right, int l, int r) const {

17 if (l > r) return 0;

18 if (l == left && r == right) return t[idx];

19

20 const int mid = (left + right) / 2;

21 return sum(idx * 2, left, mid, l, min(r, mid))

22 + sum(idx * 2 + 1, mid + 1, right, max(l, mid + 1), r);

23 }

24

25 void update(int idx, int left, int right, int pos, int val) {

26 if (left == right) {

27 t[idx] = val;

28 return;

29 }

30

31 const int mid = (left + right) / 2;

32 if (pos <= mid) update(idx * 2, left, mid, pos, val);

33 else update(idx * 2 + 1, mid + 1, right, pos, val);

34 t[idx] = t[idx * 2] + t[idx * 2 + 1];

35 }

36

37 public:

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

39 build(nums, 1, 0, n - 1);

40 }

41

42 int sum(int left, int right) const {

43 return sum(1, 0, n - 1, left, right);

44 }

45

46 void update(int pos, int val) {

47 update(1, 0, n - 1, pos, val);

48 }

49 };