Number-Theoretic Data Structures & Problem Patterns

Intuition, Vocabulary and Foundations

Many number-theory problems become easier when arithmetic facts are stored as reusable summaries. For the array $[18,30,42,70]$, the gcd of the first three values is $6$; if those values are split into blocks, the answer remains $\gcd(\gcd(18,30),42)=6$. This associativity makes gcd a good range summary, much as a warehouse records one inventory total per shelf instead of rescanning every item.

Different problems require different state. A divisor-indexed array can record how many inputs are divisible by each $d$; a residue state records a value modulo $m$; and digit DP summarizes a numeric prefix by facts such as its remainder, digit sum, or whether it is already smaller than an upper bound. Offline algorithms similarly preserve a summary while reordering queries to reduce update work.

Range lcm is also associative, but values can grow rapidly. Fenwick trees work when updates and prefix queries use an invertible or difference-friendly operation such as addition; gcd generally needs a segment tree because a previous aggregate cannot be divided out. The first design question is therefore which summary is sufficient and mergeable.

Step-by-Step Derivations and Algorithms

The baseline scans every requested range and combines its values, costing as much as $O(nq)$ for $q$ queries. Because gcd is associative and idempotent, a sparse table precomputes power-of-two intervals in $O(n\log n)$ time and answers static queries from two overlapping blocks in $O(1)$ time.

When values change, a segment tree stores the gcd or safely bounded lcm of each node interval. A point update changes one leaf and recomputes only its $O(\log n)$ ancestors; a range query merges $O(\log n)$ disjoint nodes. Fenwick trees instead excel at prefix sums and additive divisor frequencies, because addition supports differences, but a general assignment cannot repair a stored gcd from the previous aggregate alone.

For bulk arithmetic, a divisor transform computes $c_d=\sum_{d\mid x} f_x$ by visiting multiples in $O(M\log M)$ for maximum value $M$. Mo-style ordering reduces pointer movement for offline range statistics to roughly $O((n+q)\sqrt n)$ state changes under common schedules. Digit DP scans a bound and memoizes only the information that affects future digits, yielding approximately $O(LMS)$ work for $L$ positions, $M$ residues, and $S$ auxiliary states.

flowchart TD
    A["Identify query and update model"] --> B{"Static ranges?"}
    B -->|Yes| C{"Idempotent merge?"}
    C -->|Yes| D["Sparse table"]
    C -->|No| E["Prefix or disjoint structure"]
    B -->|No| F{"Online updates?"}
    F -->|Yes| G["Segment or Fenwick tree"]
    F -->|No| H["Offline ordering"]
    A --> I{"Implicit value domain?"}
    I -->|Divisors| J["Divisor transform"]
    I -->|Digit bound| K["Digit DP"]

Implementation, Complexity and Engineering

The reference implementation combines two representative patterns. GCDSegmentTree supports point assignment and half-open range queries. count_digit_sum_mod counts integers in $[0,\text{bound}]$ whose digit sum has a requested residue, using the state (position, residue, tight); leading zeroes are harmless because they add nothing to the sum.

Production code should document interval conventions, empty-range behavior, zero and sign normalization, and numeric limits. For lcm summaries, compute the division by the gcd before multiplication and check the quotient against the fixed-width limit.

from functools import lru_cache
from math import gcd


class GCDSegmentTree:
    """Point updates and gcd queries on half-open ranges [left, right)."""

    def __init__(self, values):
        if not values:
            raise ValueError("values must be nonempty")
        self.n = len(values)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        for i, value in enumerate(values):
            self.tree[self.size + i] = abs(value)
        for node in range(self.size - 1, 0, -1):
            self.tree[node] = gcd(self.tree[2 * node], self.tree[2 * node + 1])

    def update(self, index, value):
        if not 0 <= index < self.n:
            raise IndexError("index out of range")
        node = self.size + index
        self.tree[node] = abs(value)
        node //= 2
        while node:
            self.tree[node] = gcd(self.tree[2 * node], self.tree[2 * node + 1])
            node //= 2

    def query(self, left, right):
        if not 0 <= left < right <= self.n:
            raise ValueError("require 0 <= left < right <= n")
        left += self.size
        right += self.size
        answer_left = answer_right = 0
        while left < right:
            if left & 1:
                answer_left = gcd(answer_left, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                answer_right = gcd(self.tree[right], answer_right)
            left //= 2
            right //= 2
        return gcd(answer_left, answer_right)


def count_digit_sum_mod(bound, modulus, target=0):
    """Count x in [0, bound] with digit_sum(x) % modulus == target."""
    if bound < 0:
        return 0
    if modulus <= 0:
        raise ValueError("modulus must be positive")
    target %= modulus
    digits = tuple(map(int, str(bound)))

    @lru_cache(maxsize=None)
    def dp(position, residue, tight):
        if position == len(digits):
            return int(residue == target)
        limit = digits[position] if tight else 9
        total = 0
        for digit in range(limit + 1):
            total += dp(
                position + 1,
                (residue + digit) % modulus,
                tight and digit == limit,
            )
        return total

    return dp(0, 0, True)


def brute_digit_sum_mod(bound, modulus, target=0):
    return sum(
        sum(map(int, str(value))) % modulus == target % modulus
        for value in range(bound + 1)
    )


tree = GCDSegmentTree([18, 30, 42, 70])
assert tree.query(0, 3) == 6
assert tree.query(1, 4) == 2
assert tree.query(3, 4) == 70
tree.update(3, 54)
assert tree.query(0, 4) == 6
tree.update(0, -24)
assert tree.query(0, 2) == 6

for bound in (0, 9, 37, 250):
    for modulus in (1, 3, 7):
        for target in range(modulus):
            assert count_digit_sum_mod(bound, modulus, target) == (
                brute_digit_sum_mod(bound, modulus, target)
            )

try:
    tree.query(2, 2)
    raise AssertionError("empty range was accepted")
except ValueError:
    pass

try:
    count_digit_sum_mod(10, 0)
    raise AssertionError("zero modulus was accepted")
except ValueError:
    pass

print("all tests passed")

Applications, Case Studies and Exercises

These patterns transfer across different-looking tasks. A classroom range-gcd problem exposes the merge invariant directly; a production analytics system may combine divisor frequencies, offline ordering, and strict overflow limits. Digit DP indexes prefixes of an implicit set of integers rather than physical array ranges, but relies on the same principle: preserve exactly the information future decisions require.