leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0307.cpp (908B)

      1 class SegmentTree {
      2     const int n;
      3     vector<int> t = vector<int>(2 * n);
      4 
      5   public:
      6     SegmentTree(const vector<int> nums) : n(size(nums)) {
      7         for (int i = 0; i < n; i++)
      8             t[n + i] = nums[i];
      9         for (int i = n - 1; i > 0; i--)
     10             t[i] = t[i * 2] + t[i * 2 + 1];
     11     }
     12 
     13     int sum(int l, int r) const {
     14         int res = 0;
     15 
     16         for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
     17             if (l & 1) res += t[l++];
     18             if (r & 1) res += t[--r];
     19         }
     20 
     21         return res;
     22     }
     23 
     24     void update(int p, int val) {
     25         for (t[p += n] = val; p > 1; p /= 2)
     26             t[p / 2] = t[p] + t[p ^ 1];
     27     }
     28 };
     29 
     30 class NumArray {
     31     SegmentTree seg;
     32 
     33   public:
     34     NumArray(const vector<int> &nums) : seg(nums) {}
     35     void update(int index, int val) { seg.update(index, val); }
     36     int sumRange(int left, int right) const { return seg.sum(left, right); }
     37 };