ds/fenwickTree.cpp

• View this file on GitHub
• Last update: 2024-04-04 16:33:52+08:00

Verified with

• test/point_add_range_sum.test.cpp
• test/point_set_range_frequency.test.cpp
• test/rectangle_sum.test.cpp
• test/static_range_count_distinct.test.cpp
• test/vertex_add_range_contour_sum_on_tree.test.cpp
• test/vertex_get_range_contour_add_on_tree.test.cpp

Code

template<class T>
struct fenwickTree {
  const int size;
  vector<T> data;

  fenwickTree(int _size) : size(_size + 1), data(_size + 1) {}
  fenwickTree(vector<T> &init) : size(ssize(init) + 1), data(ssize(init) + 1) {
    partial_sum(init.begin(), init.end(), data.begin() + 1);
    for(int i = size - 1; i > 0; i--)
      data[i] -= data[i - (i & (-i))];
  }

  void add(int i, T d) {
    for(i += 1; i < size; i += i & (-i))
      data[i] += d;
  }

  T query(int i) {
    T res = T(0);
    for(i += 1; i > 0; i -= i & (-i))
      res += data[i];
    return res;
  }

  T query(int l, int r) { //query [l, r)
    return query(r - 1) - query(l - 1);
  }
};

#line 1 "ds/fenwickTree.cpp"
template<class T>
struct fenwickTree {
  const int size;
  vector<T> data;

  fenwickTree(int _size) : size(_size + 1), data(_size + 1) {}
  fenwickTree(vector<T> &init) : size(ssize(init) + 1), data(ssize(init) + 1) {
    partial_sum(init.begin(), init.end(), data.begin() + 1);
    for(int i = size - 1; i > 0; i--)
      data[i] -= data[i - (i & (-i))];
  }

  void add(int i, T d) {
    for(i += 1; i < size; i += i & (-i))
      data[i] += d;
  }

  T query(int i) {
    T res = T(0);
    for(i += 1; i > 0; i -= i & (-i))
      res += data[i];
    return res;
  }

  T query(int l, int r) { //query [l, r)
    return query(r - 1) - query(l - 1);
  }
};

Back to top page