comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: unit-test/data-structure/fenwick-tree.test.cpp

Depends on

Code

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

#include "src/data-structure/fenwick-tree.hpp"

#include "src/cpp-template/header/int-alias.hpp"
#include "src/math/modular-arithmetic/static-modint.hpp"

#include <cassert>
#include <iostream>

namespace luz {

  void main_() {
    { // T as i32
      FenwickTree< i32 > ft(3);

      ft.add(0, 3);
      ft.add(1, 6);
      ft.add(2, -4);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 3);
      assert(ft.sum(0, 1 + 1) == 9);
      assert(ft.sum(0, 2 + 1) == 5);
    }

    { // T as u32
      FenwickTree< u32 > ft(3);

      ft.add(0, 5);
      ft.add(1, 2);
      ft.add(2, 1);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 5);
      assert(ft.sum(0, 1 + 1) == 7);
      assert(ft.sum(0, 2 + 1) == 8);
    }

    { // T as i64
      FenwickTree< i64 > ft(3);

      ft.add(0, 1000000000000ll);
      ft.add(1, 1000000000000ll);
      ft.add(2, -2000000000000ll);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1000000000000ll);
      assert(ft.sum(0, 1 + 1) == 2000000000000ll);
      assert(ft.sum(0, 2 + 1) == 0);
    }

    { // T as u64
      FenwickTree< u64 > ft(3);

      ft.add(0, 10000000000ull);
      ft.add(1, 10000000000ull);
      ft.add(2, 10000000000ull);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 10000000000ull);
      assert(ft.sum(0, 1 + 1) == 20000000000ull);
      assert(ft.sum(0, 2 + 1) == 30000000000ull);
    }

    { // T as ModInt
      using mint = modint998244353;
      FenwickTree< mint > ft(3);

      ft.add(1, 5);
      ft.add(2, 998244352);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 0);
      assert(ft.sum(0, 1 + 1) == 5);
      assert(ft.sum(0, 2 + 1) == 4);
    }

    { // T as i32
      FenwickTree< i32 > ft({1, -10, 100, -1000});

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1);
      assert(ft.sum(0, 1 + 1) == -9);
      assert(ft.sum(0, 2 + 1) == 91);
      assert(ft.sum(0, 3 + 1) == -909);
    }

    { // T as u32
      FenwickTree< u32 > ft({1, 10, 100, 1000});

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1);
      assert(ft.sum(0, 1 + 1) == 11);
      assert(ft.sum(0, 2 + 1) == 111);
      assert(ft.sum(0, 3 + 1) == 1111);
    }

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "unit-test/data-structure/fenwick-tree.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

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

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

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

#include <cstddef>

namespace luz {

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

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/data-structure/fenwick-tree.hpp"

#include <cassert>
#include <vector>

namespace luz {

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

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

   public:
    FenwickTree() = default;

    explicit FenwickTree(usize n): n(n), vals(n + 1, T()) {}

    explicit FenwickTree(const std::vector< T > &as)
        : n(as.size()),
          vals(as.size() + 1, T()) {
      for (usize i: rep(1, as.size() + 1)) {
        vals[i] = as[i - 1];
      }
      for (usize i: rep(1, as.size() + 1)) {
        usize j = i + (i & -i);
        if (j <= as.size()) {
          vals[j] += vals[i];
        }
      }
    }

    void add(usize k, const T &v) {
      assert(k < n);
      k++;
      while (k <= n) {
        vals[k] += v;
        k += k & -k;
      }
    }

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

} // namespace luz
#line 4 "unit-test/data-structure/fenwick-tree.test.cpp"

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

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 2 "src/math/modular-arithmetic/static-modint.hpp"

#line 4 "src/math/modular-arithmetic/static-modint.hpp"

#line 6 "src/math/modular-arithmetic/static-modint.hpp"
#include <iostream>

namespace luz {

  template < u32 mod >
  class StaticPrimeModInt {
    using modint = StaticPrimeModInt;

    u32 v;

   public:
    StaticPrimeModInt(): v(0) {}

    template < typename T >
    StaticPrimeModInt(T v_) {
      i64 x = (i64)(v_ % (i64)mod);
      if (x < 0) x += mod;
      v = (u32)x;
    }

    u32 val() const {
      return v;
    }

    modint &operator+=(const modint &rhs) {
      v += rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator-=(const modint &rhs) {
      v += mod - rhs.v;
      if (v >= mod) v -= mod;
      return *this;
    }

    modint &operator*=(const modint &rhs) {
      v = (u32)(u64(1) * v * rhs.v % mod);
      return *this;
    }

    modint &operator/=(const modint &rhs) {
      *this *= rhs.inverse();
      return *this;
    }

    modint operator+() const {
      return *this;
    }

    modint operator-() const {
      return modint() - *this;
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
      return modint(lhs) += rhs;
    }

    friend modint operator-(const modint &lhs, const modint &rhs) {
      return modint(lhs) -= rhs;
    }

    friend modint operator*(const modint &lhs, const modint &rhs) {
      return modint(lhs) *= rhs;
    }

    friend modint operator/(const modint &lhs, const modint &rhs) {
      return modint(lhs) /= rhs;
    }

    friend bool operator==(const modint &lhs, const modint &rhs) {
      return lhs.v == rhs.v;
    }

    friend bool operator!=(const modint &lhs, const modint &rhs) {
      return lhs.v != rhs.v;
    }

    modint pow(i64 n) const {
      assert(0 <= n);
      modint x = *this, r = 1;
      while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
      }
      return r;
    }

    modint inverse() const {
      assert(v != 0);
      return pow(mod - 2);
    }

    static constexpr u32 get_mod() {
      return mod;
    }

    friend std::ostream &operator<<(std::ostream &os,
                                    const modint &m) {
      os << m.val();
      return os;
    }
  };

  using modint998244353  = StaticPrimeModInt< 998244353 >;
  using modint1000000007 = StaticPrimeModInt< 1000000007 >;

} // namespace luz
#line 7 "unit-test/data-structure/fenwick-tree.test.cpp"

#line 10 "unit-test/data-structure/fenwick-tree.test.cpp"

namespace luz {

  void main_() {
    { // T as i32
      FenwickTree< i32 > ft(3);

      ft.add(0, 3);
      ft.add(1, 6);
      ft.add(2, -4);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 3);
      assert(ft.sum(0, 1 + 1) == 9);
      assert(ft.sum(0, 2 + 1) == 5);
    }

    { // T as u32
      FenwickTree< u32 > ft(3);

      ft.add(0, 5);
      ft.add(1, 2);
      ft.add(2, 1);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 5);
      assert(ft.sum(0, 1 + 1) == 7);
      assert(ft.sum(0, 2 + 1) == 8);
    }

    { // T as i64
      FenwickTree< i64 > ft(3);

      ft.add(0, 1000000000000ll);
      ft.add(1, 1000000000000ll);
      ft.add(2, -2000000000000ll);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1000000000000ll);
      assert(ft.sum(0, 1 + 1) == 2000000000000ll);
      assert(ft.sum(0, 2 + 1) == 0);
    }

    { // T as u64
      FenwickTree< u64 > ft(3);

      ft.add(0, 10000000000ull);
      ft.add(1, 10000000000ull);
      ft.add(2, 10000000000ull);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 10000000000ull);
      assert(ft.sum(0, 1 + 1) == 20000000000ull);
      assert(ft.sum(0, 2 + 1) == 30000000000ull);
    }

    { // T as ModInt
      using mint = modint998244353;
      FenwickTree< mint > ft(3);

      ft.add(1, 5);
      ft.add(2, 998244352);

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 0);
      assert(ft.sum(0, 1 + 1) == 5);
      assert(ft.sum(0, 2 + 1) == 4);
    }

    { // T as i32
      FenwickTree< i32 > ft({1, -10, 100, -1000});

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1);
      assert(ft.sum(0, 1 + 1) == -9);
      assert(ft.sum(0, 2 + 1) == 91);
      assert(ft.sum(0, 3 + 1) == -909);
    }

    { // T as u32
      FenwickTree< u32 > ft({1, 10, 100, 1000});

      assert(ft.sum(0, 0) == 0);
      assert(ft.sum(0, 0 + 1) == 1);
      assert(ft.sum(0, 1 + 1) == 11);
      assert(ft.sum(0, 2 + 1) == 111);
      assert(ft.sum(0, 3 + 1) == 1111);
    }

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page