Fenwick tree (zero-based numbering), linear time construction


  • 2
    M
    class NumArray {
      vector<int> a;
    public:
      NumArray(vector<int> &nums) {
        a = nums;
        for (int i = 0; i < nums.size(); i++) {
          int j = i | i+1;
          if (j < nums.size())
            a[j] += a[i];
        }
      }
    
      void update(int i, int val) {
        val -= sumRange(i, i);
        for (; i < a.size(); i |= i+1)
          a[i] += val;
      }
    
      int sumRange(int i, int j) {
        int s = 0;
        for (j++; i != j; ) {
          if (i < j) {
            s += a[j-1];
            j &= j-1;
          } else {
            s -= a[i-1];
            i &= i-1;
          }
        }
        return s;
      }
    };
    

    https://github.com/MaskRay/LeetCode/blob/master/range-sum-query-mutable.cc


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.