データ構造/Fenwick tree/Fenwick tree
(test/data_structure/fenwick_tree/fenwick_tree.1.test.cpp)

• View this file on GitHub
• Last update: 2023-02-27 16:52:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

• Fenwick tree (binary indexed tree) (include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp)

Code

/*
 * @title データ構造/Fenwick tree/Fenwick tree
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
 */

#include <iostream>

#include "emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::FenwickTree<long long> bit(n);
  while (q--) {
    int com, x, y;
    std::cin >> com >> x >> y;
    --x;
    if (com == 0) {
      bit.add(x, y);
    } else if (com == 1) {
      --y;
      std::cout << bit.sum(x, y + 1) << '\n';
    }
  }
  return 0;
}

#line 1 "test/data_structure/fenwick_tree/fenwick_tree.1.test.cpp"
/*
 * @title データ構造/Fenwick tree/Fenwick tree
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
 */

#include <iostream>

#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"



#include <bit>
#include <vector>

namespace emthrm {

template <typename Abelian>
struct FenwickTree {
  explicit FenwickTree(const int n, const Abelian ID = 0)
      : n(n), ID(ID), data(n, ID) {}

  void add(int idx, const Abelian val) {
    for (; idx < n; idx |= idx + 1) {
      data[idx] += val;
    }
  }

  Abelian sum(int idx) const {
    Abelian res = ID;
    for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) {
      res += data[idx];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

  int lower_bound(Abelian val) const {
    if (val <= ID) [[unlikely]] return 0;
    int res = 0;
    for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1;
         mask > 0; mask >>= 1) {
      const int idx = res + mask - 1;
      if (idx < n && data[idx] < val) {
        val -= data[idx];
        res += mask;
      }
    }
    return res;
  }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data;
};

}  // namespace emthrm


#line 10 "test/data_structure/fenwick_tree/fenwick_tree.1.test.cpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::FenwickTree<long long> bit(n);
  while (q--) {
    int com, x, y;
    std::cin >> com >> x >> y;
    --x;
    if (com == 0) {
      bit.add(x, y);
    } else if (com == 1) {
      --y;
      std::cout << bit.sum(x, y + 1) << '\n';
    }
  }
  return 0;
}

Back to top page