leetcode

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

segment_tree_recursive.cpp (1407B)

      1 class SegmentTree {
      2     const int n;
      3     vector<int> t = vector<int>(4 * n);
      4 
      5     void build(const vector<int>& nums, int idx, int left, int right) {
      6         if (left == right) {
      7             t[idx] = nums[left];
      8             return;
      9         }
     10 
     11         const int mid = (left + right) / 2;
     12         build(nums, idx * 2, left, mid);
     13         build(nums, idx * 2 + 1, mid + 1, right);
     14         t[idx] = t[idx * 2] + t[idx * 2 + 1];
     15     }
     16 
     17     int sum(int idx, int left, int right, int l, int r) const {
     18         if (l > r) return 0;
     19         if (l == left && r == right) return t[idx];
     20 
     21         const int mid = (left + right) / 2;
     22         return sum(idx * 2, left, mid, l, min(r, mid))
     23              + sum(idx * 2 + 1, mid + 1, right, max(l, mid + 1), r);
     24     }
     25 
     26     void update(int idx, int left, int right, int pos, int val) {
     27         if (left == right) {
     28             t[idx] = val;
     29             return;
     30         }
     31 
     32         const int mid = (left + right) / 2;
     33         if (pos <= mid) update(idx * 2, left, mid, pos, val);
     34         else update(idx * 2 + 1, mid + 1, right, pos, val);
     35         t[idx] = t[idx * 2] + t[idx * 2 + 1];
     36     }
     37 
     38 public:
     39     SegmentTree(const vector<int> nums): n(size(nums)) {
     40         build(nums, 1, 0, n - 1);
     41     }
     42 
     43     int sum(int left, int right) const {
     44         return sum(1, 0, n - 1, left, right);
     45     }
     46 
     47     void update(int pos, int val) {
     48         update(1, 0, n - 1, pos, val);
     49     }
     50 };