src/ds/ft.hpp

• View this file on GitHub
• Last update: 2025-10-01 17:55:45+08:00
• Include: #include "src/ds/ft.hpp"

Verified with

• test/ds/fw.test.cpp

Code

template <typename T>
struct FenwickTree {
  int n;
  vector<T> c;
  FenwickTree(int n) : n(n), c(n) {}
  void add(int pos, T x) {
    for (int i = pos + 1; i <= n; i += i & -i) c[i - 1] += x;
  }
  T pref(int r) const {
    T ret = 0;
    for (int i = r; i > 0; i -= i & -i) ret += c[i - 1];
    return ret;
  }
  T sum(int l, int r) const { return pref(r) - pref(l); }
};

#line 1 "src/ds/ft.hpp"
template <typename T>
struct FenwickTree {
  int n;
  vector<T> c;
  FenwickTree(int n) : n(n), c(n) {}
  void add(int pos, T x) {
    for (int i = pos + 1; i <= n; i += i & -i) c[i - 1] += x;
  }
  T pref(int r) const {
    T ret = 0;
    for (int i = r; i > 0; i -= i & -i) ret += c[i - 1];
    return ret;
  }
  T sum(int l, int r) const { return pref(r) - pref(l); }
};

Back to top page