code/dataStructures/FT2D.cc

View this file on GitHub
Last update: 2020-10-28 19:21:59+01:00

Depends on

Verified with

tests/hackerrank/fenwick_tree_2d.cube-summation.test.cpp

Code

#include "FT.cc"
template<typename T>
struct FT2D {
  int n;
  vector<FT<T>> fts;
  FT2D(int sz1, int sz2) : n{sz1}, fts(n + 1, FT<T>(sz2)) {};
  T query(int i, int j1, int j2) {
    T sum = 0;
    for (--i; i >= 0; i = (i & (i + 1)) - 1) sum += fts[i].query(j1, j2);
    return sum;
  }
  T query(int i1, int i2, int j1, int j2) {
    return query(i2, j1, j2) - query(i1, j1, j2);
  }
  void update(int i, int j, T add) {
    for (; i < n; i |= i + 1) fts[i].update(j, add);
  }
};

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/FT.cc"
template<typename T>
struct FT {
  int n;
  vector<T> A;
  FT(int sz) : n{sz}, A(n, 0) {}
  T query(int i) {
    T sum = 0;
    for (--i; i >= 0; i = (i & (i + 1)) - 1) sum += A[i];
    return sum;
  }
  T query(int i, int j) { return query(j) - query(i); }
  void update(int i, T add) {
    for (; i < n; i |= i + 1) A[i] += add;
  }
  // lb assumes query(i, i) >= 0 forall i in [1, n]
  // returns min p >= 1, so that [1, p] >= sum
  // if [1, n] < sum, return n + 1
  /* TODO: 0 indexed
  int lb(T sum) {
    int pos = 0;
    for (int pw = 1 << 25; pw; pw >>= 1)
      if (pos + pw <= n && sum > A[pos | pw]) sum -= A[pos |= pw];
    return pos + !!sum;
  }
  */
};
#line 2 "code/dataStructures/FT2D.cc"
template<typename T>
struct FT2D {
  int n;
  vector<FT<T>> fts;
  FT2D(int sz1, int sz2) : n{sz1}, fts(n + 1, FT<T>(sz2)) {};
  T query(int i, int j1, int j2) {
    T sum = 0;
    for (--i; i >= 0; i = (i & (i + 1)) - 1) sum += fts[i].query(j1, j2);
    return sum;
  }
  T query(int i1, int i2, int j1, int j2) {
    return query(i2, j1, j2) - query(i1, j1, j2);
  }
  void update(int i, int j, T add) {
    for (; i < n; i |= i + 1) fts[i].update(j, add);
  }
};