test/aoj/dsl_2_b/fenwick-tree.test.cpp

View this file on GitHub
Last update: 2023-06-20 08:03:59+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/data-structure/fenwick-tree.hpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, q;
    std::cin >> n >> q;

    FenwickTree< u32 > ft(n);
    while (q--) {
      usize com, x, y;
      std::cin >> com >> x >> y;

      if (not com) {
        ft.add(x - 1, y);
      } else {
        std::cout << ft.sum(x - 1, y) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/aoj/dsl_2_b/fenwick-tree.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 2 "src/data-structure/fenwick-tree.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

namespace luz {

  template < typename T >
  class FenwickTree {
    usize n;
    std::vector< T > tree;

    T sum(usize k) const {
      T result{};
      while (k > 0) {
        result += tree[k];
        k -= k & -k;
      }
      return result;
    }

   public:
    FenwickTree() = default;
    explicit FenwickTree(usize n): n(n), tree(n + 1, T()) {}

    explicit FenwickTree(const std::vector< T > &as) : n(as.size()), tree(n + 1, T()) {
      std::copy(as.begin(), as.end(), tree.begin() + 1);

      for (usize i = 1; i <= n; i++) {
        usize j = i + (i & -i);
        if (j <= n) {
          tree[j] += tree[i];
        }
      }
    }

    void add(usize k, const T &v) {
      assert(0 <= k and k < n);

      k++;
      while (k <= n) {
        tree[k] += v;
        k += k & -k;
      }
    }

    T sum(usize l, usize r) const {
      assert(0 <= l and l <= r and r <= n);
      return sum(r) - sum(l);
    }
  };

} // namespace luz
#line 6 "test/aoj/dsl_2_b/fenwick-tree.test.cpp"

#include <iostream>

namespace luz {

  void main_() {
    usize n, q;
    std::cin >> n >> q;

    FenwickTree< u32 > ft(n);
    while (q--) {
      usize com, x, y;
      std::cin >> com >> x >> y;

      if (not com) {
        ft.add(x - 1, y);
      } else {
        std::cout << ft.sum(x - 1, y) << std::endl;
      }
    }
  }

} // namespace luz

int main() {
  luz::main_();
}