leetcode

Solution to some Leetcode problems written in C++

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

0307.cpp (908B)

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