Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: $\lfloor N/x \rfloor$ の配列 (src/NumberTheory/CumSumQuotient.hpp)

$\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}$ $\newcommand{\relmiddle}[1]{\mathrel{}\middle#1\mathrel{}}$

CumSumQuotient<T> クラス

添字が

$ \displaystyle S =\left\lbrace \floor{\frac{N}{x}} \relmiddle\vert x\in \mathbb{Z}, 1\leq x\leq N\right\rbrace $

の要素のみの配列.

特に数論的関数 $f(\cdot)$ の $n\in S$ までの累積和

$ \displaystyle F(n) = \sum_{i=1}^nf(i) $

の値を格納するのに用いる.

ベクトル的な演算 (加減算，スカラー倍) に対応.

メンバ変数 概要
N $N$
K $K=\floor{\sqrt{N}}$
X 実体. valarray. 直接触ることはない
  概要 計算量
operator-(F) $-F(n)$ $O(\sqrt{N})$
operator+(F,G) $F(n)+G(n)$ $O(\sqrt{N})$
operator-(F,G) $F(n)-G(n)$ $O(\sqrt{N})$
operator*(F,a) $F(n)\cdot a$ $O(\sqrt{N})$
operator*(a,F) $a\cdot F(n)$ (上と同じ) $O(\sqrt{N})$
メンバ関数 概要
CumSumQuotient(N) コンストラクタ. $N$ を渡して構築. 要素はデフォルト値.
operator[](n) $F(n)$ の値を左参照で返す.
$n\in \left\lbrace \floor{\frac{N}{x}} \relmiddle\vert x\in \mathbb{Z}, 1\leq x\leq N\right\rbrace$ を想定.
operator()(n) $F(n)$ の値を返す.
$n\in \left\lbrace \floor{\frac{N}{x}} \relmiddle\vert x\in \mathbb{Z}, 1\leq x\leq N\right\rbrace$ を想定.
sum(n) $\displaystyle F(n)= \sum_{i=1}^n f(i)$ を返す.
sum() $\displaystyle F(N)= \sum_{i=1}^N f(i)$ を返す.　sum(N) と同じ．
add(i, v) $f(i)\leftarrow f(i)+v$

Required by

Verified with

Code

#pragma once
#include <cstdint>
#include <valarray>
template <class T> struct CumSumQuotient {
 uint64_t N;
 size_t K;
 std::valarray<T> X;
 CumSumQuotient(uint64_t N): N(N), K(std::sqrt(N)), X(K + K + 1) {}
 T &operator[](uint64_t i) { return i > K ? X[K + double(N) / i] : X[i]; }
 T operator()(uint64_t i) const { return i > K ? X[K + double(N) / i] : X[i]; }
 CumSumQuotient &operator+=(const CumSumQuotient &r) { return X+= r.X, *this; }
 CumSumQuotient &operator-=(const CumSumQuotient &r) { return X-= r.X, *this; }
 CumSumQuotient &operator*=(T a) { return X*= a, *this; }
 CumSumQuotient operator-() const {
  CumSumQuotient ret= *this;
  return ret.X= -ret.X, ret;
 }
 CumSumQuotient operator+(const CumSumQuotient &r) const { return CumSumQuotient(*this)+= r; }
 CumSumQuotient operator-(const CumSumQuotient &r) const { return CumSumQuotient(*this)-= r; }
 CumSumQuotient operator*(T a) const { return CumSumQuotient(*this)*= a; }
 friend CumSumQuotient operator*(T a, const CumSumQuotient &x) { return x * a; }
 void add(uint64_t i, T v) {
  for (size_t j= std::min<uint64_t>(N / i, K) + K; j >= i; --j) X[j]+= v;
 }
 T sum() const { return X[K + 1]; }
 T sum(uint64_t i) const { return i > K ? X[K + double(N) / i] : X[i]; }
};
#line 2 "src/NumberTheory/CumSumQuotient.hpp"
#include <cstdint>
#include <valarray>
template <class T> struct CumSumQuotient {
 uint64_t N;
 size_t K;
 std::valarray<T> X;
 CumSumQuotient(uint64_t N): N(N), K(std::sqrt(N)), X(K + K + 1) {}
 T &operator[](uint64_t i) { return i > K ? X[K + double(N) / i] : X[i]; }
 T operator()(uint64_t i) const { return i > K ? X[K + double(N) / i] : X[i]; }
 CumSumQuotient &operator+=(const CumSumQuotient &r) { return X+= r.X, *this; }
 CumSumQuotient &operator-=(const CumSumQuotient &r) { return X-= r.X, *this; }
 CumSumQuotient &operator*=(T a) { return X*= a, *this; }
 CumSumQuotient operator-() const {
  CumSumQuotient ret= *this;
  return ret.X= -ret.X, ret;
 }
 CumSumQuotient operator+(const CumSumQuotient &r) const { return CumSumQuotient(*this)+= r; }
 CumSumQuotient operator-(const CumSumQuotient &r) const { return CumSumQuotient(*this)-= r; }
 CumSumQuotient operator*(T a) const { return CumSumQuotient(*this)*= a; }
 friend CumSumQuotient operator*(T a, const CumSumQuotient &x) { return x * a; }
 void add(uint64_t i, T v) {
  for (size_t j= std::min<uint64_t>(N / i, K) + K; j >= i; --j) X[j]+= v;
 }
 T sum() const { return X[K + 1]; }
 T sum(uint64_t i) const { return i > K ? X[K + double(N) / i] : X[i]; }
};
Back to top page