Prefix Sum of Binomial Coefficients
(math/prefix_sum_of_binom.hpp)

View this file on GitHub
Last update: 2026-07-13 03:08:36+09:00
Include: #include "math/prefix_sum_of_binom.hpp"

Overview

PrefixSumOfBinom<Mint> and OfflinePrefixSumOfBinom<Mint> compute

\[\sum_{k=0}^{m-1} \binom{n}{k}.\]

The online structure is useful when queries must be answered immediately. It precomputes binomial-prefix values at square-root-spaced endpoints. The offline structure stores all queries and moves between them in Mo order, using Pascal’s identity to update the current answer.

Mint must provide the static-modulus interface used by ModInt. The modulus must be prime, odd for the offline structure, and larger than every queried n.

API

template <class Mint>
struct PrefixSumOfBinom {
    explicit PrefixSumOfBinom(int maximum);
    int maximum() const;
    Mint query(int n, int m) const;
};

template <class Mint>
struct OfflinePrefixSumOfBinom {
    int query_count() const;
    bool empty() const;
    void reserve(int query_capacity);
    void clear();
    int add_query(int n, int m);
    std::vector<Mint> calculate() const;
};

Method	Description	Complexity
`PrefixSumOfBinom(maximum)`	Precomputes data for every `0 <= n <= maximum`.	$O(N\sqrt N)$ time and memory
`maximum()`	Returns the largest supported `n`.	$O(1)$
`query(n, m)`	Returns the half-open prefix through `m - 1`.	$O(\sqrt N)$
`query_count()`	Returns the number of stored offline queries.	$O(1)$
`empty()`	Tests whether the offline batch is empty.	$O(1)$
`reserve(query_capacity)`	Reserves storage for offline queries.	$O(Q)$ in the worst case
`clear()`	Removes all offline queries.	$O(Q)$
`add_query(n, m)`	Stores a query and returns its insertion-order ID.	Amortized $O(1)$
`calculate()`	Returns answers in insertion order.	$O((N+Q)\sqrt Q)$ time and $O(N+Q)$ memory

Here $N$ is the largest queried or constructed n, and $Q$ is the number of offline queries.

Behavioral Notes

The range in k is half-open: query(n, m) sums 0 <= k < m.
m == 0 returns zero.
Values m > n + 1 are clamped to n + 1, so the result is 2^n.
The online constructor asserts that maximum is nonnegative and smaller than the modulus. Each query asserts 0 <= n <= maximum and m >= 0.
calculate() does not clear or mutate the offline query batch. Query IDs and returned positions use insertion order.
The online version has relatively high memory use. Prefer the offline version when all queries are known beforehand.

Example

#include "math/modint.hpp"
#include "math/prefix_sum_of_binom.hpp"

#include <iostream>

int main() {
    using Mint = m1une::math::modint998244353;
    m1une::math::PrefixSumOfBinom<Mint> prefix(1000);

    // 1 + 5 + 10 = 16
    std::cout << prefix.query(5, 3) << '\n';

    m1une::math::OfflinePrefixSumOfBinom<Mint> offline;
    offline.add_query(5, 3);
    offline.add_query(4, 5);
    const auto answers = offline.calculate();
    std::cout << answers[0] << ' ' << answers[1] << '\n';
}

Depends on

Combinatorics (math/combinatorics.hpp)

Required by

Math All (math/all.hpp)

Verified with

Code

#ifndef M1UNE_MATH_PREFIX_SUM_OF_BINOM_HPP
#define M1UNE_MATH_PREFIX_SUM_OF_BINOM_HPP 1

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>

#include "combinatorics.hpp"

namespace m1une {
namespace math {

// Answers sum_{k=0}^{m-1} binom(n, k) after square-root decomposition.
template <class Mint>
struct PrefixSumOfBinom {
   private:
    int _maximum;
    int _block_size;
    Combinatorics<Mint> _combinations;
    std::vector<Mint> _powers_of_two;
    std::vector<std::vector<Mint>> _data;

    Mint _block_prefix(int n, int block) const {
        const int endpoint = block * _block_size;
        if (n <= endpoint) return _powers_of_two[n];
        return _data[block][n - endpoint] * _combinations.inverse_factorial(endpoint);
    }

    Mint _binom_sum(int n, int left, int right) const {
        __uint128_t sum = 0;
        for (int k = left; k < right; k++) {
            sum += static_cast<__uint128_t>(_combinations.inverse_factorial(k).val()) *
                   _combinations.inverse_factorial(n - k).val();
        }
        const uint32_t reduced = static_cast<uint32_t>(sum % Mint::mod());
        return Mint::raw(reduced) * _combinations.factorial(n);
    }

   public:
    explicit PrefixSumOfBinom(int maximum)
        : _maximum(maximum),
          _block_size(std::max(1, int(std::sqrt(static_cast<double>(maximum) + 1)))),
          _combinations(maximum),
          _powers_of_two(maximum + 1, Mint(1)) {
        assert(maximum >= 0);

        for (int n = 0; n < maximum; n++) {
            _powers_of_two[n + 1] = _powers_of_two[n] + _powers_of_two[n];
        }

        const int block_count = maximum / (2 * _block_size) + 3;
        _data.resize(block_count);
        for (int block = 0; block < block_count; block++) {
            const int endpoint = block * _block_size;
            if (endpoint > maximum) continue;

            std::vector<Mint>& values = _data[block];
            values.resize(maximum - endpoint + 1);
            values[0] = _powers_of_two[endpoint] * _combinations.factorial(endpoint);
            for (int offset = 0; offset < maximum - endpoint; offset++) {
                values[offset + 1] =
                    values[offset] + values[offset] -
                    _combinations.factorial(offset + endpoint) *
                        _combinations.inverse_factorial(offset);
            }
        }
    }

    int maximum() const {
        return _maximum;
    }

    // Returns sum_{k=0}^{m-1} binom(n, k). Values m > n + 1 are clamped.
    Mint query(int n, int m) const {
        assert(0 <= n && n <= _maximum);
        assert(m >= 0);
        m = std::min(m, n + 1);
        if (m == 0) return Mint(0);
        if (2 * m > n + 1) {
            return _powers_of_two[n] - query(n, n + 1 - m);
        }

        const int endpoint = m - 1;
        const int block = endpoint / _block_size;
        const int lower = block * _block_size;
        const int upper = (block + 1) * _block_size;
        if (endpoint - lower <= upper - endpoint) {
            return _block_prefix(n, block) + _binom_sum(n, lower + 1, endpoint + 1);
        }
        return _block_prefix(n, block + 1) - _binom_sum(n, endpoint + 1, upper + 1);
    }
};

// Batches the same queries and evaluates them in Mo order with linear memory.
template <class Mint>
struct OfflinePrefixSumOfBinom {
   private:
    std::vector<std::pair<int, int>> _queries;

   public:
    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _queries.empty();
    }

    void reserve(int query_capacity) {
        assert(query_capacity >= 0);
        _queries.reserve(query_capacity);
    }

    void clear() {
        _queries.clear();
    }

    // Adds sum_{k=0}^{m-1} binom(n, k) and returns its insertion-order ID.
    int add_query(int n, int m) {
        assert(n >= 0);
        assert(m >= 0);
        m = std::min(m, n + 1);
        const int id = query_count();
        _queries.emplace_back(n, m);
        return id;
    }

    std::vector<Mint> calculate() const {
        const int count = query_count();
        std::vector<Mint> answers(count);
        if (count == 0) return answers;

        int maximum = 0;
        for (const auto& query : _queries) maximum = std::max(maximum, query.first);
        assert(static_cast<uint64_t>(maximum) < Mint::mod());
        assert(Mint::mod() % 2 == 1);
        Combinatorics<Mint> combinations(maximum);

        const int block_size =
            std::max(1, int(maximum / std::sqrt(static_cast<double>(count))));
        std::vector<int> order(count);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int first, int second) {
            const int first_block = _queries[first].first / block_size;
            const int second_block = _queries[second].first / block_size;
            if (first_block != second_block) return first_block < second_block;
            if (first_block & 1) return _queries[first].second > _queries[second].second;
            return _queries[first].second < _queries[second].second;
        });

        int n = 0;
        int m = 0;
        Mint answer = 0;
        const Mint inverse_two = Mint(2).inv();
        for (int id : order) {
            const int next_n = _queries[id].first;
            const int next_m = _queries[id].second;
            while (n < next_n) {
                answer += answer;
                answer -= combinations.binom(n, m - 1);
                n++;
            }
            while (n > next_n) {
                answer += combinations.binom(n - 1, m - 1);
                answer *= inverse_two;
                n--;
            }
            while (m < next_m) answer += combinations.binom(n, m++);
            while (m > next_m) answer -= combinations.binom(n, --m);
            answers[id] = answer;
        }
        return answers;
    }
};

}  // namespace math
}  // namespace m1une

#endif  // M1UNE_MATH_PREFIX_SUM_OF_BINOM_HPP

#line 1 "math/prefix_sum_of_binom.hpp"



#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>

#line 1 "math/combinatorics.hpp"



#line 7 "math/combinatorics.hpp"

namespace m1une {
namespace math {

template <class Mint>
struct Combinatorics {
   private:
    std::vector<Mint> _factorial;
    std::vector<Mint> _inverse_factorial;

   public:
    explicit Combinatorics(int maximum = 0) : _factorial(1, Mint(1)), _inverse_factorial(1, Mint(1)) {
        ensure(maximum);
    }

    int maximum() const {
        return int(_factorial.size()) - 1;
    }

    void ensure(int maximum) {
        assert(maximum >= 0);
        assert(static_cast<uint64_t>(maximum) < Mint::mod());
        if (maximum <= this->maximum()) return;

        const int old_maximum = this->maximum();
        _factorial.resize(maximum + 1);
        _inverse_factorial.resize(maximum + 1);
        for (int i = old_maximum + 1; i <= maximum; i++) {
            _factorial[i] = _factorial[i - 1] * Mint(i);
        }
        _inverse_factorial[maximum] = _factorial[maximum].inv();
        for (int i = maximum; i > old_maximum; i--) {
            _inverse_factorial[i - 1] = _inverse_factorial[i] * Mint(i);
        }
    }

    Mint factorial(int n) const {
        assert(0 <= n && n <= maximum());
        return _factorial[n];
    }

    Mint inverse_factorial(int n) const {
        assert(0 <= n && n <= maximum());
        return _inverse_factorial[n];
    }

    Mint inverse(int n) const {
        assert(1 <= n && n <= maximum());
        return _factorial[n - 1] * _inverse_factorial[n];
    }

    Mint binom(int n, int k) const {
        if (k < 0 || k > n) return Mint(0);
        assert(n <= maximum());
        return _factorial[n] * _inverse_factorial[k] * _inverse_factorial[n - k];
    }

    Mint perm(int n, int k) const {
        if (k < 0 || k > n) return Mint(0);
        assert(n <= maximum());
        return _factorial[n] * _inverse_factorial[n - k];
    }

    Mint multiset(int types, int count) const {
        if (types < 0 || count < 0) return Mint(0);
        if (types == 0) return Mint(count == 0);
        const long long total = static_cast<long long>(types) + count - 1;
        assert(total <= maximum());
        return binom(static_cast<int>(total), count);
    }

    Mint catalan(int n) const {
        assert(n >= 0);
        const long long doubled = 2LL * n;
        assert(doubled <= maximum());
        return binom(int(doubled), n) - binom(int(doubled), n + 1);
    }
};

}  // namespace math
}  // namespace m1une


#line 13 "math/prefix_sum_of_binom.hpp"

namespace m1une {
namespace math {

// Answers sum_{k=0}^{m-1} binom(n, k) after square-root decomposition.
template <class Mint>
struct PrefixSumOfBinom {
   private:
    int _maximum;
    int _block_size;
    Combinatorics<Mint> _combinations;
    std::vector<Mint> _powers_of_two;
    std::vector<std::vector<Mint>> _data;

    Mint _block_prefix(int n, int block) const {
        const int endpoint = block * _block_size;
        if (n <= endpoint) return _powers_of_two[n];
        return _data[block][n - endpoint] * _combinations.inverse_factorial(endpoint);
    }

    Mint _binom_sum(int n, int left, int right) const {
        __uint128_t sum = 0;
        for (int k = left; k < right; k++) {
            sum += static_cast<__uint128_t>(_combinations.inverse_factorial(k).val()) *
                   _combinations.inverse_factorial(n - k).val();
        }
        const uint32_t reduced = static_cast<uint32_t>(sum % Mint::mod());
        return Mint::raw(reduced) * _combinations.factorial(n);
    }

   public:
    explicit PrefixSumOfBinom(int maximum)
        : _maximum(maximum),
          _block_size(std::max(1, int(std::sqrt(static_cast<double>(maximum) + 1)))),
          _combinations(maximum),
          _powers_of_two(maximum + 1, Mint(1)) {
        assert(maximum >= 0);

        for (int n = 0; n < maximum; n++) {
            _powers_of_two[n + 1] = _powers_of_two[n] + _powers_of_two[n];
        }

        const int block_count = maximum / (2 * _block_size) + 3;
        _data.resize(block_count);
        for (int block = 0; block < block_count; block++) {
            const int endpoint = block * _block_size;
            if (endpoint > maximum) continue;

            std::vector<Mint>& values = _data[block];
            values.resize(maximum - endpoint + 1);
            values[0] = _powers_of_two[endpoint] * _combinations.factorial(endpoint);
            for (int offset = 0; offset < maximum - endpoint; offset++) {
                values[offset + 1] =
                    values[offset] + values[offset] -
                    _combinations.factorial(offset + endpoint) *
                        _combinations.inverse_factorial(offset);
            }
        }
    }

    int maximum() const {
        return _maximum;
    }

    // Returns sum_{k=0}^{m-1} binom(n, k). Values m > n + 1 are clamped.
    Mint query(int n, int m) const {
        assert(0 <= n && n <= _maximum);
        assert(m >= 0);
        m = std::min(m, n + 1);
        if (m == 0) return Mint(0);
        if (2 * m > n + 1) {
            return _powers_of_two[n] - query(n, n + 1 - m);
        }

        const int endpoint = m - 1;
        const int block = endpoint / _block_size;
        const int lower = block * _block_size;
        const int upper = (block + 1) * _block_size;
        if (endpoint - lower <= upper - endpoint) {
            return _block_prefix(n, block) + _binom_sum(n, lower + 1, endpoint + 1);
        }
        return _block_prefix(n, block + 1) - _binom_sum(n, endpoint + 1, upper + 1);
    }
};

// Batches the same queries and evaluates them in Mo order with linear memory.
template <class Mint>
struct OfflinePrefixSumOfBinom {
   private:
    std::vector<std::pair<int, int>> _queries;

   public:
    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _queries.empty();
    }

    void reserve(int query_capacity) {
        assert(query_capacity >= 0);
        _queries.reserve(query_capacity);
    }

    void clear() {
        _queries.clear();
    }

    // Adds sum_{k=0}^{m-1} binom(n, k) and returns its insertion-order ID.
    int add_query(int n, int m) {
        assert(n >= 0);
        assert(m >= 0);
        m = std::min(m, n + 1);
        const int id = query_count();
        _queries.emplace_back(n, m);
        return id;
    }

    std::vector<Mint> calculate() const {
        const int count = query_count();
        std::vector<Mint> answers(count);
        if (count == 0) return answers;

        int maximum = 0;
        for (const auto& query : _queries) maximum = std::max(maximum, query.first);
        assert(static_cast<uint64_t>(maximum) < Mint::mod());
        assert(Mint::mod() % 2 == 1);
        Combinatorics<Mint> combinations(maximum);

        const int block_size =
            std::max(1, int(maximum / std::sqrt(static_cast<double>(count))));
        std::vector<int> order(count);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int first, int second) {
            const int first_block = _queries[first].first / block_size;
            const int second_block = _queries[second].first / block_size;
            if (first_block != second_block) return first_block < second_block;
            if (first_block & 1) return _queries[first].second > _queries[second].second;
            return _queries[first].second < _queries[second].second;
        });

        int n = 0;
        int m = 0;
        Mint answer = 0;
        const Mint inverse_two = Mint(2).inv();
        for (int id : order) {
            const int next_n = _queries[id].first;
            const int next_m = _queries[id].second;
            while (n < next_n) {
                answer += answer;
                answer -= combinations.binom(n, m - 1);
                n++;
            }
            while (n > next_n) {
                answer += combinations.binom(n - 1, m - 1);
                answer *= inverse_two;
                n--;
            }
            while (m < next_m) answer += combinations.binom(n, m++);
            while (m > next_m) answer -= combinations.binom(n, --m);
            answers[id] = answer;
        }
        return answers;
    }
};

}  // namespace math
}  // namespace m1une

m1une's library

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

Prefix Sum of Binomial Coefficients
(math/prefix_sum_of_binom.hpp)

Overview

API

Behavioral Notes

Example

Depends on

Required by

Verified with

Code

Prefix Sum of Binomial Coefficients (math/prefix_sum_of_binom.hpp)

Overview

API

Behavioral Notes

Example

Depends on

Required by

Verified with

Code

Prefix Sum of Binomial Coefficients
(math/prefix_sum_of_binom.hpp)