DataStructure/FenwickTree.cpp

• View this file on GitHub
• Last update: 2022-05-27 17:24:30+09:00
• Link: http://na-o-s.hateblo.jp/entry/2014/07/13/031143

Code

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct FenwickTree{
  vector<T> fenwick;
  int n;

  FenwickTree(int n):
    fenwick(vector<T>(n+1, 0)), n(n) {}

  T sum(int i) {
    if (!i) return 0;
    return fenwick[i] + sum(i-(i&-i));
  }

  T sum(int i, int j){
    // half-open Terval
    return sum(j-1) - sum(i-1);
  }

  void add(int i, T x) {
    if (i > n) return;
    fenwick[i] += x;
    add(i+(i&-i), x);
  }
};

//1-indexed
//  http://na-o-s.hateblo.jp/entry/2014/07/13/031143

#line 1 "DataStructure/FenwickTree.cpp"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct FenwickTree{
  vector<T> fenwick;
  int n;

  FenwickTree(int n):
    fenwick(vector<T>(n+1, 0)), n(n) {}

  T sum(int i) {
    if (!i) return 0;
    return fenwick[i] + sum(i-(i&-i));
  }

  T sum(int i, int j){
    // half-open Terval
    return sum(j-1) - sum(i-1);
  }

  void add(int i, T x) {
    if (i > n) return;
    fenwick[i] += x;
    add(i+(i&-i), x);
  }
};

//1-indexed
//  http://na-o-s.hateblo.jp/entry/2014/07/13/031143

Back to top page