Detailed mathematical approach

Problem Summary

Let \(A^{(0)}=(0,0,\dots,0)\) be an array of length \(n\). A tribonacci sequence modulo \(n\) is generated by

$t_0=t_1=0,\qquad t_2=1,\qquad t_k\equiv t_{k-1}+t_{k-2}+t_{k-3}\pmod{n}\quad (k\ge 3).$

At step \(i\ge 1\), the update uses two consecutive residues from that sequence:

$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$

The array changes by adding \(d_i\) to position \(p_i\), so

$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$

while every other entry stays unchanged. After each update we ask for the maximum subarray sum, with the empty subarray allowed:

$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$

The required output is a sum of these query values over a specified interval of steps. It is convenient to write

$S(n;L_0,U)=\sum_{i=L_0+1}^{U} M_i.$

The challenge is that \(n\) and \(U\) are both very large, so recomputing a full maximum-subarray scan from scratch after every point update would be far too slow.

Mathematical Approach

The key observation is that a maximum subarray query can be represented by a small summary for each segment, and those summaries can be merged associatively. Because each step changes only one array entry, only one local block has to be recomputed directly.

Step 1: Describe the Deterministic Update Stream

The tribonacci recurrence determines every update completely. The even-indexed residue \(t_{2i-2}\) selects the position, and the odd-indexed residue \(t_{2i-1}\) determines the increment.

Since \(0\le t_k\lt n\), the update size always lies in the symmetric interval

$1-n\le d_i\le n-1.$

So the array evolves by a long sequence of signed point updates. The problem is not probabilistic: once \(n\) is fixed, the entire stream is fixed.

Step 2: Summarize Any Segment by Four Numbers

For any contiguous segment \(X\), define four quantities:

$T(X)=\text{total sum of }X,$

$P(X)=\max(0,\text{largest prefix sum of }X),$

$Q(X)=\max(0,\text{largest suffix sum of }X),$

$M(X)=\max(0,\text{largest subarray sum inside }X).$

More explicitly, if \(X=(x_0,x_1,\dots,x_{m-1})\), then

$T(X)=\sum_{j=0}^{m-1}x_j,$

$P(X)=\max_{0\le k\le m}\sum_{j=0}^{k-1}x_j,$

$Q(X)=\max_{0\le k\le m}\sum_{j=k}^{m-1}x_j,$

$M(X)=\max\left(0,\max_{0\le l\le r\lt m}\sum_{j=l}^{r}x_j\right).$

The empty prefix, empty suffix, and empty subarray are all allowed, which is why \(P(X)\), \(Q(X)\), and \(M(X)\) never become negative.

Step 3: Merge Two Adjacent Segments

Suppose a segment is split into adjacent left and right parts, \(X=LR\). If the summaries of \(L\) and \(R\) are known, then the summary of \(X\) is forced:

$T(X)=T(L)+T(R),$

$P(X)=\max\bigl(P(L),\,T(L)+P(R)\bigr),$

$Q(X)=\max\bigl(Q(R),\,T(R)+Q(L)\bigr),$

$M(X)=\max\bigl(M(L),\,M(R),\,Q(L)+P(R)\bigr).$

The first three formulas are immediate. For the maximum subarray, there are exactly three possibilities: the optimal subarray lies wholly in the left part, wholly in the right part, or crosses the boundary. In the crossing case it must be a best suffix of \(L\) followed by a best prefix of \(R\).

Because these merge rules depend only on the two child summaries, they can be used in a segment tree.

Step 4: Compress the Tree by Blocking the Array

A full segment tree over all \(n\) entries would work mathematically, but for the actual scale it is wasteful. The implementations therefore divide the array into fixed-size blocks of length \(b\), and only whole blocks become leaves of the outer tree.

If

$B=\left\lceil\frac{n}{b}\right\rceil,$

then the outer tree has \(B\) logical leaves instead of \(n\). Each leaf stores the four-number summary of one block, and the root summary represents the whole array. Therefore the current answer after every update is simply

$M_i=M\bigl(A^{(i)}\bigr),$

which is the final component of the root summary.

Step 5: Recompute Only the Touched Block

A point update changes exactly one block. Inside that block, a single changed entry can alter the best prefix, the best suffix, and the best internal subarray in many places, so the simplest correct strategy is to recompute that block from scratch.

That recomputation is still cheap because the block size is fixed. A left-to-right scan produces the total sum, the best prefix sum, and the best internal subarray sum. A right-to-left scan produces the best suffix sum. Once the refreshed block summary is known, the outer tree is updated along one root-to-leaf path using the merge formulas from Step 3.

This is the entire reason the method is fast: each update performs one \(O(b)\) local rebuild and one \(O(\log B)\) tree repair, instead of one \(O(n)\) global maximum-subarray scan.

Worked Example: \(n=5\) and the First Six Updates

For \(n=5\), the tribonacci residues begin

$0,0,1,1,2,4,2,3,4,4,1,4,\dots$

So the first six update pairs \((p_i,d_i)\) are

$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $

Applying them to the initially zero array gives

$\begin{aligned} A^{(1)}&=(-4,0,0,0,0),\\ A^{(2)}&=(-4,-2,0,0,0),\\ A^{(3)}&=(-4,-2,4,0,0),\\ A^{(4)}&=(-4,-2,6,0,0),\\ A^{(5)}&=(-4,-2,6,0,4),\\ A^{(6)}&=(-4,2,6,0,4). \end{aligned}$

The corresponding maximum subarray sums are

$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $

Hence

$S(5;0,6)=0+0+4+6+10+12=32,$

which is one of the small checkpoints reproduced by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan. They first generate the tribonacci residues needed for the requested upper step bound, because each update consumes two consecutive residues.

The C++ and Java implementations store the full array, partition it into fixed-size blocks, and build a segment tree whose leaves are block summaries rather than single elements. After a point update, the affected block is rescanned to rebuild its four summary values, and those values are merged upward until the root is refreshed.

The root summary always contains the current maximum subarray sum for the whole array, so each step contributes that root value to the running total whenever the step index lies inside the requested summation interval. The Python implementation is only a thin wrapper: it delegates the heavy computation to the compiled implementation instead of duplicating the data structure in pure Python.

The accumulated answer can grow well beyond an ordinary fixed-width signed integer if many large query values are added, so the implementations use an integer representation wide enough for the final total.

Complexity Analysis

Let \(U\) be the largest step index that must be processed, let \(b\) be the fixed block size, and let \(B=\lceil n/b\rceil\). Precomputing the tribonacci residues up to index \(2U-1\) takes \(O(U)\) time and \(O(U)\) extra memory in the reference implementations.

Each update changes one array cell, rebuilds one block in \(O(b)\) time, and repairs the outer tree in \(O(\log B)\) time. Therefore the total update cost through step \(U\) is

$O\bigl(U(b+\log B)\bigr).$

Because \(b\) is a fixed constant in the implementations, this is effectively near-linear in the number of processed updates, with only a small logarithmic factor from the tree. The total memory usage is

$O(n+B+U)=O(n+U),$

since \(B\le n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=663
2. Tribonacci numbers: Wikipedia — Tribonacci number
3. Maximum subarray problem: Wikipedia — Maximum subarray problem
4. Segment tree: Wikipedia — Segment tree