leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

segment_tree_recursive.cpp (1407B)

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