src/structure/bit_index_tree.hpp

• View this file on GitHub
• Last update: 2022-12-30 21:24:59+09:00
• Include: #include "src/structure/bit_index_tree.hpp"

Code

#pragma once

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

template <typename T> struct BIT {
private:
  int n;
  vector<T> bit;

public:
  BIT(int n) : n(n), bit(n + 1, 0) {}

  // i is 0-indexed.
  void add(int i, T x) {
    for (++i; i <= n + 1; i += i & -i) {
      bit[i] += x;
    }
  }

  // [0, i), i is 0-indexed.
  T sum(int i) {
    T res = 0;
    for (; i > 0; i -= i & -i) {
      res += bit[i];
    }
    return res;
  }

  // [l, r), l and r is 0-indexed.
  T sum(int l, int r) { return sum(r) - sum(l); }
};

#line 2 "src/structure/bit_index_tree.hpp"

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

template <typename T> struct BIT {
private:
  int n;
  vector<T> bit;

public:
  BIT(int n) : n(n), bit(n + 1, 0) {}

  // i is 0-indexed.
  void add(int i, T x) {
    for (++i; i <= n + 1; i += i & -i) {
      bit[i] += x;
    }
  }

  // [0, i), i is 0-indexed.
  T sum(int i) {
    T res = 0;
    for (; i > 0; i -= i & -i) {
      res += bit[i];
    }
    return res;
  }

  // [l, r), l and r is 0-indexed.
  T sum(int l, int r) { return sum(r) - sum(l); }
};

Back to top page