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.
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.
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.
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.
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.
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.
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.
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.
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.
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\).
Sei \(A^{(0)}=(0,0,\dots,0)\) ein Array der Länge \(n\). Zuerst wird eine Tribonacci-Folge modulo \(n\) erzeugt:
$$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).$$
Im Schritt \(i\ge 1\) liefern zwei aufeinanderfolgende Residuen die Punktaktualisierung
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
Dann wird an Position \(p_i\) der Wert \(d_i\) addiert, also
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
während alle anderen Einträge unverändert bleiben. Nach jedem Update wird die maximale Teilarray-Summe mit erlaubtem leerem Teilarray abgefragt:
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
Gesucht ist die Summe dieser Werte über ein vorgegebenes Schrittintervall. Zweckmäßig ist die Schreibweise
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U} M_i.$$
Da sowohl \(n\) als auch \(U\) sehr groß sind, wäre eine vollständige Neuberechnung der maximalen Teilarray-Summe nach jedem einzelnen Punktupdate viel zu teuer.
Der entscheidende Gedanke ist, dass sich eine Maximum-Teilarray-Anfrage durch eine kleine Segmentzusammenfassung darstellen lässt, und dass diese Zusammenfassungen assoziativ zusammengeführt werden können. Da jeder Schritt nur einen einzigen Arrayeintrag ändert, muss lokal auch nur ein einziger Block direkt neu berechnet werden.
Die Tribonacci-Rekurrenz bestimmt jeden Update-Schritt vollständig. Das gerade Residuum \(t_{2i-2}\) wählt die Position, das ungerade Residuum \(t_{2i-1}\) bestimmt die Größe der Änderung.
Wegen \(0\le t_k\lt n\) liegt jedes Inkrement im Bereich
$$1-n\le d_i\le n-1.$$
Das Array entwickelt sich also durch eine lange Folge vorzeichenbehafteter Punktupdates. An diesem Problem ist nichts zufällig: Ist \(n\) fest, dann ist auch der gesamte Update-Strom fest vorgegeben.
Für ein beliebiges zusammenhängendes Segment \(X\) definieren wir vier Größen:
$$T(X)=\text{Gesamtsumme von }X,$$
$$P(X)=\max(0,\text{größte Präfixsumme von }X),$$
$$Q(X)=\max(0,\text{größte Suffixsumme von }X),$$
$$M(X)=\max(0,\text{größte Teilarray-Summe innerhalb von }X).$$
Für \(X=(x_0,x_1,\dots,x_{m-1})\) bedeutet das explizit
$$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).$$
Leeres Präfix, leeres Suffix und leeres Teilarray sind erlaubt. Deshalb können \(P(X)\), \(Q(X)\) und \(M(X)\) nie negativ werden.
Sei \(X=LR\) die Konkatenation eines linken und eines rechten Teilsegments. Kennt man die Zusammenfassungen von \(L\) und \(R\), dann ist die Zusammenfassung von \(X\) eindeutig bestimmt:
$$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).$$
Die ersten drei Formeln sind direkt klar. Für die maximale Teilarray-Summe gibt es genau drei Fälle: Das optimale Teilarray liegt ganz links, ganz rechts oder es überschreitet die Schnittstelle. Im dritten Fall besteht es aus einem besten Suffix von \(L\) und einem besten Präfix von \(R\).
Weil diese Merge-Regeln nur die beiden Kinderzusammenfassungen benötigen, eignen sie sich ideal für einen Segmentbaum.
Ein voller Segmentbaum über alle \(n\) Positionen wäre mathematisch korrekt, aber für die reale Größenordnung unnötig speicherintensiv. Deshalb teilen die Implementierungen das Array in Blöcke fester Länge \(b\), und nur ganze Blöcke werden zu Blättern des äußeren Baums.
Mit
$$B=\left\lceil\frac{n}{b}\right\rceil$$
hat der äußere Baum also \(B\) logische Blätter statt \(n\). Jedes Blatt speichert die Viererzusammenfassung eines Blocks, und die Wurzel repräsentiert das gesamte Array. Die aktuelle Antwort nach jedem Schritt ist damit einfach
$$M_i=M\bigl(A^{(i)}\bigr),$$
also die letzte Komponente der Wurzelzusammenfassung.
Ein Punktupdate verändert genau einen Block. Innerhalb dieses Blocks kann schon eine einzige geänderte Zahl viele Präfixe, Suffixe und innere Teilarrays beeinflussen. Daher ist die einfachste korrekte Strategie, den ganzen Block direkt neu auszuwerten.
Das bleibt günstig, weil die Blockgröße fest ist. Ein Links-nach-rechts-Durchlauf liefert Gesamtsumme, beste Präfixsumme und beste innere Teilarray-Summe. Ein Rechts-nach-links-Durchlauf liefert die beste Suffixsumme. Danach wird nur noch der Pfad dieses einen Blattes bis zur Wurzel mit den Formeln aus Schritt 3 repariert.
Genau dadurch wird das Verfahren schnell: pro Update ein lokaler Neuaufbau in \(O(b)\) und eine Baumreparatur in \(O(\log B)\), statt einer globalen Maximum-Teilarray-Berechnung in \(O(n)\).
Für \(n=5\) beginnen die Tribonacci-Residuen mit
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
Daraus ergeben sich die ersten sechs Update-Paare \((p_i,d_i)\):
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
Ausgehend vom Nullarray erhält man
$$\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}$$
Die zugehörigen maximalen Teilarray-Summen sind
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $$
Somit folgt
$$S(5;0,6)=0+0+4+6+10+12=32,$$
genau einer der kleinen Kontrollwerte der Implementierung.
Die C++, Python- und Java-Implementierungen folgen alle demselben mathematischen Plan. Zuerst werden die Tribonacci-Residuen bis zur benötigten oberen Schrittgrenze erzeugt, denn jeder Schritt verbraucht zwei aufeinanderfolgende Werte.
Die C++- und Java-Implementierungen speichern das vollständige Array, teilen es in Blöcke fester Größe und bauen einen Segmentbaum, dessen Blätter Blockzusammenfassungen statt Einzelelementen sind. Nach einem Punktupdate wird der betroffene Block erneut gescannt, um seine vier Kennzahlen neu zu berechnen; anschließend werden diese Werte bis zur Wurzel zusammengeführt.
Die Wurzel enthält jederzeit die aktuelle maximale Teilarray-Summe des gesamten Arrays. Liegt der Schrittindex im geforderten Summationsintervall, wird genau dieser Wurzelwert zur laufenden Gesamtsumme addiert. Die Python-Implementierung ist nur ein schlanker Wrapper und delegiert die eigentliche Schwerarbeit an die kompilierte Implementierung, statt die Datenstruktur selbst noch einmal in reinem Python nachzubauen.
Da die aufsummierte Endantwort deutlich größer werden kann als ein gewöhnlicher fester Maschinentyp bequem abdeckt, verwenden die Implementierungen einen hinreichend breiten Ganzzahltyp für das Gesamtergebnis.
Sei \(U\) die größte zu verarbeitende Schrittzahl, \(b\) die feste Blockgröße und \(B=\lceil n/b\rceil\). Das Vorberechnen der Tribonacci-Residuen bis Index \(2U-1\) kostet in den Referenzimplementierungen \(O(U)\) Zeit und \(O(U)\) zusätzlichen Speicher.
Jedes Update verändert genau eine Arrayzelle, berechnet einen Block in \(O(b)\) neu und repariert den äußeren Baum in \(O(\log B)\). Die Gesamtkosten bis Schritt \(U\) betragen daher
$$O\bigl(U(b+\log B)\bigr).$$
Weil \(b\) in den Implementierungen konstant ist, ist das praktisch fast linear in der Zahl der verarbeiteten Updates, mit nur einem kleinen logarithmischen Zusatzfaktor. Der Speicherverbrauch ist
$$O(n+B+U)=O(n+U),$$
da \(B\le n\) gilt.
\(A^{(0)}=(0,0,\dots,0)\) olacak şekilde uzunluğu \(n\) olan bir dizi ile başlanır. Önce mod \(n\) tribonacci dizisi üretilir:
$$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).$$
\(i\ge 1\) adımında iki ardışık kalıntı şu noktasal güncellemeyi belirler:
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
Buna göre \(p_i\) konumundaki elemana \(d_i\) eklenir, yani
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
diğer tüm konumlar aynı kalır. Her güncellemeden sonra, boş alt diziye de izin verilecek şekilde maksimum alt dizi toplamı sorulur:
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
İstenen çıktı, bu sorgu değerlerinin belirli bir adım aralığındaki toplamıdır. Bunu
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U} M_i$$
şeklinde yazmak kullanışlıdır. Hem \(n\) hem de \(U\) çok büyük olduğu için, her nokta güncellemesinden sonra baştan sona yeniden Kadane taraması yapmak yeterince hızlı değildir.
Temel gözlem şudur: maksimum alt dizi sorgusu, her segment için küçük bir özetle temsil edilebilir ve bu özetler birleşmeli biçimde birleştirilebilir. Her adım yalnızca tek bir hücreyi değiştirdiği için doğrudan yeniden hesaplanması gereken yer de sadece tek bir yerel bloktur.
Tribonacci bağıntısı her güncellemeyi tamamen belirler. Çift indeksli kalıntı \(t_{2i-2}\) konumu seçer; tek indeksli kalıntı \(t_{2i-1}\) ise değişimin büyüklüğünü verir.
\(0\le t_k\lt n\) olduğu için her artış ya da azalış şu aralıktadır:
$$1-n\le d_i\le n-1.$$
Dolayısıyla dizi, işaretli nokta güncellemelerinden oluşan uzun bir akışla evrilir. Problem rastgele değildir; \(n\) sabitlendiği anda tüm güncelleme akışı da sabitlenmiş olur.
Herhangi bir bitişik \(X\) segmenti için şu dört büyüklüğü tanımlayalım:
$$T(X)=\text{\(X\) segmentinin toplamı},$$
$$P(X)=\max(0,\text{\(X\) içindeki en büyük önek toplamı}),$$
$$Q(X)=\max(0,\text{\(X\) içindeki en büyük sonek toplamı}),$$
$$M(X)=\max(0,\text{\(X\) içindeki en büyük alt dizi toplamı}).$$
Eğer \(X=(x_0,x_1,\dots,x_{m-1})\) ise bunlar açıkça
$$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)$$
şeklindedir. Boş önek, boş sonek ve boş alt diziye izin verildiği için \(P(X)\), \(Q(X)\) ve \(M(X)\) negatif olmaz.
\(X=LR\) olacak şekilde bir segmenti sol ve sağ parçaya ayıralım. \(L\) ve \(R\) özetleri biliniyorsa \(X\) özeti tek anlamlıdır:
$$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).$$
İlk üç formül doğrudandır. Maksimum alt dizi için ise sadece üç olasılık vardır: en iyi alt dizi tamamen soldadır, tamamen sağdadır ya da sınırı geçer. Sınırı geçen durumda, yapı zorunlu olarak soldaki en iyi sonek ile sağdaki en iyi öneğin birleşimidir.
Bu birleşim kuralları yalnızca çocuk özetlerine bağlı olduğu için segment ağacında kusursuz biçimde kullanılabilir.
Tüm \(n\) eleman üzerinde tam bir segment ağacı kurmak matematiksel olarak doğrudur, fakat gerçek boyutlarda gereksiz bellek maliyeti yaratır. Bu yüzden implementasyonlar diziyi sabit uzunluklu \(b\) bloklarına ayırır ve dış ağacın yapraklarını tek tek elemanlar değil, tüm bloklar oluşturur.
Eğer
$$B=\left\lceil\frac{n}{b}\right\rceil$$
ise dış ağaç \(n\) yerine \(B\) mantıksal yaprak taşır. Her yaprak bir bloğun dört bileşenli özetini tutar, kök de tüm diziyi temsil eder. Böylece her adımın cevabı doğrudan
$$M_i=M\bigl(A^{(i)}\bigr)$$
olur; yani kök özetinin son bileşeni anlık cevaptır.
Bir nokta güncellemesi yalnızca bir bloğu değiştirir. Fakat bu tek değişiklik, o blok içindeki pek çok önek, sonek ve iç alt dizi adayını etkileyebilir. Bu yüzden en sade ve doğru strateji, ilgili bloğu baştan sona yeniden taramaktır.
Blok boyu sabit olduğu için bu ucuzdur. Soldan sağa yapılan bir tarama blok toplamını, en iyi önek toplamını ve blok içindeki en iyi alt dizi toplamını verir. Sağdan sola yapılan ikinci tarama da en iyi sonek toplamını verir. Sonra sadece bu yapraktan köke giden yol, Adım 3'teki birleşim formülleriyle güncellenir.
Yöntemin hız kazanmasının nedeni budur: her güncellemede bir adet \(O(b)\) yerel yeniden kurulum ve bir adet \(O(\log B)\) ağaç düzeltmesi yapılır; \(O(n)\) boyutunda küresel tarama yapılmaz.
\(n=5\) olduğunda tribonacci kalıntılarının başlangıcı
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
şeklindedir. Buna göre ilk altı güncelleme çifti \((p_i,d_i)\) şöyledir:
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
Sıfır dizisinden başlayıp bunları uygularsak
$$\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}$$
elde edilir. Buna karşılık maksimum alt dizi toplamları
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12) $$
olur. Dolayısıyla
$$S(5;0,6)=0+0+4+6+10+12=32,$$
ki bu, implementasyonun küçük doğrulama değerlerinden biridir.
C++, Python ve Java implementasyonları aynı matematiksel planı izler. Önce istenen üst adım sınırına kadar gerekli tribonacci kalıntıları üretilir; çünkü her güncelleme iki ardışık kalıntı kullanır.
C++ ve Java implementasyonları tam diziyi bellekte tutar, onu sabit boylu bloklara ayırır ve yaprakları tek tek elemanlar değil, blok özetleri olan bir segment ağacı kurar. Noktasal güncelleme geldiğinde ilgili blok yeniden taranarak dört özet değeri çıkarılır; ardından bu yeni özet köke kadar birleştirilir.
Kök özeti, o andaki tüm dizi için maksimum alt dizi toplamını içerdiğinden, adım numarası toplama aralığına düştüğünde bu kök değeri cevaba eklenir. Python implementasyonu ağır işi doğrudan kendisi yapmaz; bunun yerine hesaplamayı derlenmiş implementasyona devreden ince bir katmandır.
Toplanan sonucun büyüklüğü sıradan sabit genişlikli tam sayı sınırlarını rahatlıkla aşabildiği için implementasyonlar nihai toplamı yeterince geniş bir tamsayı gösteriminde tutar.
\(U\) işlenecek en büyük adım numarası, \(b\) sabit blok boyu ve \(B=\lceil n/b\rceil\) olsun. Referans implementasyonlarda \(2U-1\) indeksine kadar tribonacci kalıntılarını önceden üretmek \(O(U)\) zaman ve \(O(U)\) ek bellek gerektirir.
Her güncelleme bir dizi hücresini değiştirir, bir bloğu \(O(b)\) zamanda yeniden kurar ve dış ağacı \(O(\log B)\) zamanda onarır. Bu nedenle \(U\) adımına kadar toplam güncelleme maliyeti
$$O\bigl(U(b+\log B)\bigr)$$
olur. \(b\) implementasyonlarda sabit olduğundan, bu maliyet pratikte güncelleme sayısına göre neredeyse doğrusaldır; yalnızca küçük bir logaritmik ağaç faktörü kalır. Toplam bellek kullanımı ise
$$O(n+B+U)=O(n+U)$$
şeklindedir; çünkü \(B\le n\).
Sea \(A^{(0)}=(0,0,\dots,0)\) un arreglo de longitud \(n\). Primero se genera una sucesión tribonacci módulo \(n\):
$$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).$$
En el paso \(i\ge 1\), dos residuos consecutivos determinan la actualización puntual
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
Se suma entonces \(d_i\) en la posición \(p_i\), es decir,
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
mientras que las demás entradas permanecen iguales. Después de cada actualización se consulta la suma máxima de subarreglo, permitiendo también el subarreglo vacío:
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
La salida pedida es la suma de esos valores en un intervalo dado de pasos. Conviene escribir
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U} M_i.$$
Como \(n\) y \(U\) son enormes, volver a ejecutar un barrido completo de suma máxima tras cada actualización puntual sería demasiado lento.
La observación central es que una consulta de máximo subarreglo puede describirse con un resumen pequeño para cada segmento, y esos resúmenes se combinan de forma asociativa. Como cada paso modifica una sola posición, solo hay que recalcular directamente un bloque local.
La recurrencia tribonacci fija por completo cada actualización. El residuo de índice par \(t_{2i-2}\) elige la posición, y el residuo de índice impar \(t_{2i-1}\) determina el incremento.
Dado que \(0\le t_k\lt n\), siempre se cumple
$$1-n\le d_i\le n-1.$$
Por tanto, el arreglo evoluciona mediante una larga secuencia de actualizaciones puntuales con signo. No hay ninguna parte aleatoria: una vez fijado \(n\), queda fijado todo el flujo de actualizaciones.
Para un segmento contiguo cualquiera \(X\), definimos:
$$T(X)=\text{suma total de }X,$$
$$P(X)=\max(0,\text{mayor suma prefijo de }X),$$
$$Q(X)=\max(0,\text{mayor suma sufijo de }X),$$
$$M(X)=\max(0,\text{mayor suma de subarreglo dentro de }X).$$
Si \(X=(x_0,x_1,\dots,x_{m-1})\), eso significa de forma explícita
$$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).$$
Se permiten el prefijo vacío, el sufijo vacío y el subarreglo vacío, de modo que \(P(X)\), \(Q(X)\) y \(M(X)\) nunca son negativos.
Supongamos que \(X=LR\), donde \(L\) es la parte izquierda y \(R\) la derecha. Si conocemos los resúmenes de \(L\) y \(R\), entonces el de \(X\) viene dado por
$$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).$$
Las tres primeras fórmulas son inmediatas. Para la máxima suma de subarreglo solo hay tres casos posibles: el mejor subarreglo está enteramente a la izquierda, enteramente a la derecha, o cruza la frontera. En el caso de cruce, necesariamente es un mejor sufijo de \(L\) seguido por un mejor prefijo de \(R\).
Como estas reglas de fusión dependen solo de los resúmenes hijos, encajan de forma natural en un árbol de segmentos.
Un árbol de segmentos completo sobre las \(n\) posiciones sería correcto desde el punto de vista matemático, pero demasiado costoso para el tamaño real del problema. Por eso las implementaciones dividen el arreglo en bloques de longitud fija \(b\), y las hojas del árbol exterior representan bloques completos en vez de elementos individuales.
Si
$$B=\left\lceil\frac{n}{b}\right\rceil,$$
entonces el árbol exterior tiene \(B\) hojas lógicas en lugar de \(n\). Cada hoja guarda el resumen de cuatro cantidades para un bloque, y la raíz resume el arreglo completo. Por tanto, la respuesta actual después de cada paso es simplemente
$$M_i=M\bigl(A^{(i)}\bigr),$$
es decir, la última componente del resumen almacenado en la raíz.
Una actualización puntual modifica exactamente un bloque. Dentro de ese bloque, un solo cambio puede alterar muchas opciones de prefijo, sufijo y subarreglo interno. La estrategia correcta más simple es volver a calcular ese bloque desde cero.
Eso sigue siendo barato porque el tamaño del bloque es fijo. Un recorrido de izquierda a derecha produce la suma total, la mejor suma prefijo y la mejor suma de subarreglo dentro del bloque. Un recorrido de derecha a izquierda produce la mejor suma sufijo. Después solo hay que actualizar el camino desde esa hoja hasta la raíz usando las fórmulas del Paso 3.
Ahí está toda la ganancia del método: por actualización se hace un recomputo local en \(O(b)\) y una reparación del árbol en \(O(\log B)\), en vez de un barrido global de \(O(n)\).
Para \(n=5\), los residuos tribonacci comienzan así:
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
De ahí salen los seis primeros pares \((p_i,d_i)\):
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
Aplicándolos al arreglo inicialmente nulo obtenemos
$$\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}$$
Las sumas máximas de subarreglo correspondientes son
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $$
Por consiguiente,
$$S(5;0,6)=0+0+4+6+10+12=32,$$
que coincide con uno de los valores de comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero generan los residuos tribonacci hasta la cota superior de pasos requerida, porque cada actualización consume dos residuos consecutivos.
Las implementaciones en C++ y Java almacenan el arreglo completo, lo dividen en bloques de tamaño fijo y construyen un árbol de segmentos cuyas hojas son resúmenes de bloques en lugar de elementos sueltos. Tras una actualización puntual, el bloque afectado se recorre de nuevo para reconstruir sus cuatro cantidades resumen, y luego esos datos se propagan hacia arriba hasta refrescar la raíz.
La raíz contiene siempre la suma máxima de subarreglo del arreglo entero, de modo que cuando el índice del paso cae dentro del intervalo de suma pedido, ese valor de la raíz se añade al acumulado. La implementación en Python es solo una capa ligera: delega el cálculo pesado en la implementación compilada en lugar de reproducir la estructura de datos en Python puro.
La respuesta acumulada puede superar con facilidad el rango cómodo de un entero fijo ordinario, así que las implementaciones usan una representación entera lo bastante amplia para guardar el total final.
Sea \(U\) el mayor paso que debe procesarse, sea \(b\) el tamaño fijo del bloque y sea \(B=\lceil n/b\rceil\). En las implementaciones de referencia, precalcular los residuos tribonacci hasta el índice \(2U-1\) cuesta \(O(U)\) tiempo y \(O(U)\) memoria adicional.
Cada actualización modifica una celda del arreglo, reconstruye un bloque en \(O(b)\) y repara el árbol exterior en \(O(\log B)\). Por tanto, el coste total hasta el paso \(U\) es
$$O\bigl(U(b+\log B)\bigr).$$
Como \(b\) es una constante fija en las implementaciones, el comportamiento es prácticamente casi lineal en el número de actualizaciones procesadas, con un pequeño factor logarítmico debido al árbol. El consumo total de memoria es
$$O(n+B+U)=O(n+U),$$
ya que \(B\le n\).
设 \(A^{(0)}=(0,0,\dots,0)\) 是一个长度为 \(n\) 的数组。先生成一个模 \(n\) 的 tribonacci 序列：
$$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).$$
在第 \(i\ge 1\) 次更新中，使用这个序列的两个相邻值：
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
也就是说，把位置 \(p_i\) 上的值增加 \(d_i\)，即
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
其余位置保持不变。每次更新完成后，都要查询当前数组的最大子段和，并且允许空子段：
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
题目最终要求的是某个步数区间内这些查询值的总和。写成
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U}M_i$$
会比较清楚。真正的难点在于 \(n\) 和 \(U\) 都非常大，所以不能在每次单点更新后再对整个数组重新跑一遍最大子段和算法。
核心思想是：对任意一个连续区间，只要保存四个量，就足以描述这个区间在“最大子段和”意义下的全部必要信息；而两个相邻区间的四元摘要可以用固定公式合并。由于每一步只改动一个位置，所以真正需要直接重算的也只有那个位置所在的局部块。
tribonacci 递推一旦给定，整个更新序列就是完全确定的。偶数下标的残基 \(t_{2i-2}\) 给出被修改的位置，奇数下标的残基 \(t_{2i-1}\) 给出本次增量。
因为 \(0\le t_k\lt n\)，所以每一步的增量都满足
$$1-n\le d_i\le n-1.$$
也就是说，数组是在一个确定的“带正负号的单点更新流”之下演化的，并不存在随机性。只要 \(n\) 固定，所有位置和增量就全部固定下来。
对任意连续区间 \(X\)，定义以下四个量：
$$T(X)=\text{\(X\) 的总和},$$
$$P(X)=\max(0,\text{\(X\) 的最大前缀和}),$$
$$Q(X)=\max(0,\text{\(X\) 的最大后缀和}),$$
$$M(X)=\max(0,\text{\(X\) 内部的最大子段和}).$$
如果 \(X=(x_0,x_1,\dots,x_{m-1})\)，那么它们可以更明确地写成
$$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).$$
这里允许空前缀、空后缀和空子段，所以 \(P(X)\)、\(Q(X)\)、\(M(X)\) 永远不会是负数。这一点与实现完全一致，因为一旦所有可选子段和都为负，就直接取空子段，对应值为 \(0\)。
设一个更大的区间 \(X\) 由相邻的左右两部分拼成，即 \(X=LR\)。如果已经知道 \(L\) 和 \(R\) 的四元摘要，那么 \(X\) 的摘要由下式唯一决定：
$$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).$$
这些式子的含义很直接。总和当然是左右总和之和；最大前缀和要么完全落在左边，要么先吃掉整个左边再加上右边的最佳前缀；最大后缀和同理。至于最大子段和，只有三种可能：最优子段完全在左边、完全在右边，或者跨越中间边界。跨越边界时，它一定是“左边最佳后缀 + 右边最佳前缀”。
正因为合并只依赖子区间摘要，所以这个问题非常适合用线段树式的分治结构来维护。
如果直接对全部 \(n\) 个元素建立完整线段树，从数学上当然可行，但在本题规模下并不划算。实现采用的办法是先把数组划分成固定长度为 \(b\) 的块，然后在线段树中把“整块”当作叶子，而不是把单个元素当作叶子。
若块数为
$$B=\left\lceil\frac{n}{b}\right\rceil,$$
那么外层树只需要 \(B\) 个逻辑叶子，而不是 \(n\) 个。每个叶子保存一个整块的四元摘要，根节点则对应整个数组。因此每次更新后的答案就是
$$M_i=M\bigl(A^{(i)}\bigr),$$
也就是根摘要中的“最大子段和”这一项。这样做的本质收益，是把树上的节点数量从按元素维护的大规模常数开销，压缩到了按块维护。
一次单点更新只会改变一个位置，所以也只会影响一个块。块外的元素完全没变，因此块外所有块摘要也不需要重新扫描。真正变化的只有那个被触及的块，以及从该块叶子到树根的合并结果。
在块内部，虽然只改了一个值，但最佳前缀、最佳后缀、块内最佳子段都可能受到连锁影响，所以最稳妥的做法就是把整块从头扫一遍。由于块长 \(b\) 是固定常数，这个重算代价是可控的。
具体来说，一次从左到右的扫描可以同时得到块总和、最大前缀和、块内最大子段和；再做一次从右到左的扫描就能得到最大后缀和。拿到新块摘要以后，再沿着外层树往上逐层合并，就能恢复全局答案。
当 \(n=5\) 时，tribonacci 残基开头是
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
因此前六个更新对 \((p_i,d_i)\) 为
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
从全零数组开始依次更新，可得
$$\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}$$
这六步对应的最大子段和为
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $$
于是
$$S(5;0,6)=0+0+4+6+10+12=32,$$
这正好与实现中的小规模校验值一致。
C++、Python 和 Java 实现都遵循同一套数学结构。首先，它们会生成直到所需最大步数为止的 tribonacci 残基，因为每一步更新都要消耗两个相邻残基。
C++ 和 Java 实现会保存完整数组，把它分成固定大小的块，并建立一棵“块线段树”：树叶代表整块的摘要，而不是单个元素。每次单点更新后，程序先把受影响的块重新扫描，得到新的四元摘要，再沿树向上合并到根。
根节点摘要始终保存整个数组当前的最大子段和，所以只要步数进入要求累加的区间，就把根节点中的这个值加入答案。Python 实现本身并没有再用纯 Python 重写这一套数据结构，而是作为一层轻量封装，把真正的重计算交给编译后的实现去完成。
由于最终需要累加很多次查询结果，总答案可能远超普通定宽整数的舒适范围，因此实现会使用足够宽的整数表示来保存最终总和。
设需要处理到的最大步数为 \(U\)，块长为固定常数 \(b\)，块数为 \(B=\lceil n/b\rceil\)。参考实现会预先生成到下标 \(2U-1\) 为止的 tribonacci 残基，这一步需要 \(O(U)\) 时间和 \(O(U)\) 额外空间。
每次更新只改一个数组位置，重算一个块需要 \(O(b)\) 时间，修复外层树需要 \(O(\log B)\) 时间，因此处理到第 \(U\) 步的总更新成本是
$$O\bigl(U(b+\log B)\bigr).$$
因为实现中的 \(b\) 是固定常数，所以整体上几乎就是对更新次数的近线性复杂度，只额外带一个很小的对数因子。总空间复杂度为
$$O(n+B+U)=O(n+U),$$
这里用了 \(B\le n\) 这一事实。
Пусть \(A^{(0)}=(0,0,\dots,0)\) — массив длины \(n\). Сначала строится последовательность трибоначчи по модулю \(n\):
$$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).$$
На шаге \(i\ge 1\) два соседних остатка задают точечное обновление
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
То есть к элементу с индексом \(p_i\) прибавляется \(d_i\), а значит
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
все остальные элементы не меняются. После каждого обновления нужно найти максимальную сумму подмассива, разрешая и пустой подмассив:
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
Итоговый ответ — сумма этих значений на заданном диапазоне шагов. Удобно обозначить
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U}M_i.$$
Главная трудность в том, что и \(n\), и \(U\) очень велики, поэтому полный пересчет максимальной суммы подмассива после каждого точечного изменения был бы слишком медленным.
Ключевая идея состоит в том, что для любого отрезка массива достаточно хранить четыре числа, полностью описывающие его поведение относительно задачи о максимальном подмассиве. Эти четырехкомпонентные сводки можно объединять ассоциативно. Поскольку на каждом шаге меняется только один элемент, напрямую пересчитывать нужно лишь один локальный блок.
Рекуррентное соотношение трибоначчи полностью фиксирует все обновления. Остаток с четным индексом \(t_{2i-2}\) выбирает позицию, а остаток с нечетным индексом \(t_{2i-1}\) задает величину изменения.
Так как \(0\le t_k\lt n\), для каждого шага выполнено
$$1-n\le d_i\le n-1.$$
Следовательно, массив эволюционирует под действием длинного детерминированного потока знаковых точечных обновлений. Никакой случайности здесь нет: как только задано \(n\), весь поток обновлений определен однозначно.
Для любого непрерывного отрезка \(X\) введем четыре величины:
$$T(X)=\text{сумма всех элементов }X,$$
$$P(X)=\max(0,\text{максимальная сумма префикса }X),$$
$$Q(X)=\max(0,\text{максимальная сумма суффикса }X),$$
$$M(X)=\max(0,\text{максимальная сумма подмассива внутри }X).$$
Если \(X=(x_0,x_1,\dots,x_{m-1})\), то это можно записать явно так:
$$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).$$
Пустой префикс, пустой суффикс и пустой подмассив разрешены, поэтому \(P(X)\), \(Q(X)\) и \(M(X)\) никогда не становятся отрицательными. Это точно соответствует соглашению, использованному в реализации.
Пусть \(X=LR\), где \(L\) — левая часть, а \(R\) — правая. Если известны четырехкомпонентные сводки для \(L\) и \(R\), то сводка для \(X\) вычисляется по формулам
$$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).$$
Первые три формулы очевидны. Для максимального подмассива есть ровно три варианта: он целиком лежит слева, целиком лежит справа или пересекает границу. В последнем случае он обязательно состоит из лучшего суффикса левой части и лучшего префикса правой части.
Поскольку правило объединения зависит только от дочерних сводок, его естественно использовать в дереве отрезков.
Полное дерево отрезков по всем \(n\) элементам математически корректно, но для реального масштаба задачи слишком тяжеловесно по памяти. Поэтому реализации сначала разбивают массив на блоки фиксированной длины \(b\), и листья внешнего дерева представляют целые блоки, а не отдельные элементы.
Если
$$B=\left\lceil\frac{n}{b}\right\rceil,$$
то внешнее дерево имеет \(B\) логических листьев вместо \(n\). Каждый лист хранит четырехкомпонентную сводку своего блока, а корень соответствует всему массиву. Значит, после любого обновления текущий ответ равен
$$M_i=M\bigl(A^{(i)}\bigr),$$
то есть последней компоненте сводки, находящейся в корне.
Одно точечное обновление затрагивает ровно один блок. Вне этого блока значения массива не изменились вообще, поэтому сводки остальных блоков остаются прежними. Пересчитывать нужно только сам затронутый блок и значения на пути от его листа к корню дерева.
Хотя внутри блока изменился всего один элемент, он может повлиять на многие префиксы, суффиксы и внутренние подмассивы. Поэтому самый надежный и простой способ — просканировать весь блок заново. Так как длина блока фиксирована, эта операция остается дешевой.
Проход слева направо дает сумму блока, максимальную префиксную сумму и максимальную внутреннюю сумму подмассива. Проход справа налево дает максимальную суффиксную сумму. После этого новое четырехкомпонентное описание блока поднимается вверх по дереву при помощи формул объединения из шага 3.
Для \(n=5\) последовательность остатков трибоначчи начинается так:
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
Следовательно, первые шесть пар \((p_i,d_i)\) равны
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
Если стартовать с нулевого массива, то получаем
$$\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}$$
Соответствующие максимальные суммы подмассивов равны
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $$
Поэтому
$$S(5;0,6)=0+0+4+6+10+12=32,$$
что совпадает с одним из малых контрольных значений, воспроизводимых реализацией.
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они строят остатки трибоначчи до нужной верхней границы шагов, потому что каждый шаг использует два соседних остатка.
Реализации на C++ и Java хранят весь массив, делят его на блоки фиксированного размера и строят дерево отрезков, в листьях которого лежат не отдельные элементы, а сводки целых блоков. После точечного обновления затронутый блок пересчитывается заново, а затем новая сводка поднимается вверх до корня.
Корень в любой момент содержит текущую максимальную сумму подмассива для всего массива, поэтому, если номер шага попадает в требуемый интервал суммирования, именно это значение добавляется к ответу. Реализация на Python не дублирует структуру данных на чистом Python: она служит легкой оболочкой и передает тяжелую вычислительную часть скомпилированной реализации.
Так как итоговая сумма может оказаться существенно больше диапазона обычного знакового машинного целого, реализации используют достаточно широкий целочисленный тип для накопления окончательного результата.
Пусть \(U\) — максимальный обрабатываемый шаг, \(b\) — фиксированная длина блока, а \(B=\lceil n/b\rceil\). Предварительное вычисление остатков трибоначчи до индекса \(2U-1\) занимает \(O(U)\) времени и \(O(U)\) дополнительной памяти в эталонных реализациях.
Каждое обновление меняет одну ячейку массива, пересчитывает один блок за \(O(b)\) и восстанавливает внешнее дерево за \(O(\log B)\). Поэтому полная стоимость обработки до шага \(U\) равна
$$O\bigl(U(b+\log B)\bigr).$$
Поскольку \(b\) в реализациях является константой, алгоритм практически близок к линейному по числу обработанных шагов, с небольшим логарифмическим множителем из-за дерева. Общий объем памяти равен
$$O(n+B+U)=O(n+U),$$
так как \(B\le n\).
لنأخذ المصفوفة \(A^{(0)}=(0,0,\dots,0)\) ذات الطول \(n\). أولاً نولد متتالية tribonacci بترديد \(n\):
$$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).$$
في الخطوة \(i\ge 1\) يحدد حدان متتاليان من هذه المتتالية تحديثًا نقطيًا على المصفوفة:
$$p_i=t_{2i-2},\qquad d_i=2t_{2i-1}-n+1.$$
أي نضيف \(d_i\) إلى الموضع \(p_i\)، وبذلك
$$A^{(i)}_{p_i}=A^{(i-1)}_{p_i}+d_i,$$
بينما تبقى بقية العناصر كما هي. بعد كل تحديث نطلب أكبر مجموع لمقطع متصل، مع السماح أيضًا بالمقطع الفارغ:
$$M_i=\max\left(0,\max_{0\le l\le r\lt n}\sum_{j=l}^{r}A^{(i)}_j\right).$$
المطلوب في النهاية هو جمع هذه القيم على مجال معين من الخطوات. ومن المناسب أن نكتب
$$S(n;L_0,U)=\sum_{i=L_0+1}^{U}M_i.$$
الصعوبة الأساسية أن \(n\) و\(U\) كبيران جدًا، ولذلك فإن إعادة حساب أكبر مجموع مقطع من الصفر بعد كل تحديث نقطي ستكون بطيئة أكثر من اللازم.
الفكرة المحورية هي أن استعلام «أكبر مجموع لمقطع متصل» يمكن تمثيله بملخص صغير لكل قطعة من المصفوفة، وهذه الملخصات يمكن دمجها بصيغة ثابتة. وبما أن كل خطوة تغيّر عنصرًا واحدًا فقط، فإن الجزء الذي يحتاج إلى إعادة حساب مباشرة هو كتلة محلية واحدة فقط.
علاقة tribonacci تحدد كل تحديث بشكل كامل. الباقي ذو الفهرس الزوجي \(t_{2i-2}\) يختار الموضع، والباقي ذو الفهرس الفردي \(t_{2i-1}\) يعطي قيمة الزيادة أو النقصان.
وبما أن \(0\le t_k\lt n\)، فإن كل تغير يحقق
$$1-n\le d_i\le n-1.$$
إذًا فالمصفوفة تتطور عبر سلسلة طويلة من التحديثات النقطية ذات الإشارة الموجبة أو السالبة. لا يوجد أي عنصر عشوائي هنا؛ ما إن تثبت قيمة \(n\) حتى يصبح تسلسل التحديثات كله محددًا سلفًا.
لكل قطعة متجاورة \(X\) نعرّف أربع كميات:
\(T(X)\): المجموع الكلي لعناصر \(X\).
\(P(X)\): أكبر مجموع بادئة في \(X\)، مع السماح بالبادئة الفارغة.
\(Q(X)\): أكبر مجموع لاحقة في \(X\)، مع السماح باللاحقة الفارغة.
\(M(X)\): أكبر مجموع لمقطع داخلي في \(X\)، أو \(0\) إذا كان المقطع الفارغ أفضل.
إذا كانت \(X=(x_0,x_1,\dots,x_{m-1})\)، فإن ذلك يكتب صراحة على الصورة
$$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).$$
نحن نسمح بالبادئة الفارغة واللاحقة الفارغة والمقطع الفارغ، ولهذا لا تصبح \(P(X)\) و\(Q(X)\) و\(M(X)\) سالبة أبدًا. وهذا يطابق تمامًا أسلوب التنفيذ الفعلي في الحلول.
إذا كانت القطعة الكبيرة \(X\) ناتجة عن ضم جزء أيسر \(L\) وجزء أيمن \(R\)، أي \(X=LR\)، فإن ملخص \(X\) يُستنتج مباشرة من ملخصي \(L\) و\(R\):
$$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).$$
المعادلات الثلاث الأولى واضحة. أما بالنسبة لأكبر مجموع مقطع، فهناك ثلاث حالات فقط: إما أن يكون المقطع الأمثل كله في اليسار، أو كله في اليمين، أو يعبر الحد الفاصل بينهما. وفي الحالة الثالثة لا بد أن يكون مكوّنًا من أفضل لاحقة في \(L\) متبوعة بأفضل بادئة في \(R\).
وبما أن قاعدة الدمج تعتمد فقط على ملخصي الجزأين، فهي مناسبة جدًا لبنية شجرة المقاطع.
بناء شجرة مقاطع كاملة على كل عنصر من عناصر المصفوفة صحيح من الناحية الرياضية، لكنه مكلف بلا داعٍ على حجم المسألة الحقيقي. لذلك تقسم الحلول المصفوفة إلى كتل ثابتة الطول \(b\)، وتصبح أوراق الشجرة الخارجية ممثلة للكتل الكاملة بدلًا من العناصر المنفردة.
إذا كان عدد الكتل
$$B=\left\lceil\frac{n}{b}\right\rceil,$$
فإن الشجرة الخارجية تحتوي على \(B\) أوراق منطقية بدلًا من \(n\). كل ورقة تخزن الملخص الرباعي لكتلة واحدة، أما الجذر فيمثل المصفوفة كلها. لذلك يكون الجواب بعد كل تحديث هو ببساطة
$$M_i=M\bigl(A^{(i)}\bigr),$$
أي أن القيمة المطلوبة موجودة مباشرة في المركبة الأخيرة من ملخص الجذر.
التحديث النقطي يغيّر كتلة واحدة فقط. وخارج هذه الكتلة لا يتغير شيء إطلاقًا، ولذلك تبقى ملخصات بقية الكتل صحيحة كما هي. ما يجب إصلاحه هو الكتلة المصابة نفسها ثم المسار الصاعد منها إلى الجذر.
مع أن عنصرًا واحدًا فقط قد تغير داخل الكتلة، فإنه قد يؤثر في أفضل بادئة وأفضل لاحقة وأفضل مقطع داخلي في أماكن كثيرة. لذلك فإن أبسط استراتيجية صحيحة هي إعادة مسح الكتلة كلها من البداية. وبما أن طول الكتلة ثابت، فإن هذا المسح يبقى رخيصًا.
المسح من اليسار إلى اليمين يعطي مجموع الكتلة وأفضل بادئة وأفضل مقطع داخلي، والمسح من اليمين إلى اليسار يعطي أفضل لاحقة. بعد ذلك نأخذ هذا الملخص الجديد ونصعد به في الشجرة مستخدمين قواعد الدمج المذكورة في الخطوة السابقة.
عندما \(n=5\)، تبدأ بواقي tribonacci كما يلي:
$$0,0,1,1,2,4,2,3,4,4,1,4,\dots$$
ومن ثم تكون أول ستة أزواج تحديث \((p_i,d_i)\) هي
$$ (0,-4),\ (1,-2),\ (2,4),\ (2,2),\ (4,4),\ (1,4). $$
انطلاقًا من المصفوفة الصفرية نحصل على
$$\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}$$
أما قيم أكبر مجموع مقطع بعد كل خطوة فهي
$$ (M_1,M_2,M_3,M_4,M_5,M_6)=(0,0,4,6,10,12). $$
إذًا
$$S(5;0,6)=0+0+4+6+10+12=32,$$
وهذه إحدى قيم التحقق الصغيرة التي تعيدها الحلول نفسها.
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. في البداية تولد بواقي tribonacci اللازمة حتى أعلى خطوة مطلوبة، لأن كل تحديث يحتاج إلى حدين متتاليين من هذه البواقي.
تحتفظ تطبيقات C++ وJava بالمصفوفة كاملة، وتقسمها إلى كتل ذات حجم ثابت، ثم تبني شجرة مقاطع تكون أوراقها ملخصات كتل لا عناصر منفردة. بعد أي تحديث نقطي تعاد قراءة الكتلة المتأثرة لحساب قيمها الأربع من جديد، ثم تُدمج هذه القيم صعودًا حتى يتحدث الجذر.
يحمل الجذر دائمًا قيمة أكبر مجموع مقطع للمصفوفة كلها، ولذلك عندما يقع رقم الخطوة داخل مجال الجمع المطلوب تُضاف قيمة الجذر إلى الجواب التراكمي. أما تطبيق Python فليس إعادة كتابة مستقلة لهذه البنية، بل هو طبقة خفيفة تفوض الحساب الثقيل إلى التنفيذ المترجم.
ولأن مجموع القيم المطلوبة قد يتجاوز بسهولة مجال عدد صحيح عادي ذي عرض ثابت، فإن الحلول تستخدم تمثيلًا عدديًا واسعًا بما يكفي لاستيعاب الناتج النهائي.
لنرمز إلى أكبر خطوة معالجة بـ \(U\)، وإلى حجم الكتلة الثابت بـ \(b\)، وإلى عدد الكتل بـ \(B=\lceil n/b\rceil\). إن التوليد المسبق لبواقي tribonacci حتى الفهرس \(2U-1\) يكلف \(O(U)\) زمنًا و\(O(U)\) ذاكرة إضافية في الحلول المرجعية.
كل تحديث يغيّر خلية واحدة في المصفوفة، ويعيد حساب كتلة واحدة في \(O(b)\)، ثم يصلح الشجرة الخارجية في \(O(\log B)\). لذلك فإن الكلفة الكلية حتى الخطوة \(U\) تساوي
$$O\bigl(U(b+\log B)\bigr).$$
وبما أن \(b\) ثابت في هذه الحلول، فإن الأداء عمليًا شبه خطي في عدد التحديثات المعالجة، مع عامل لوغاريتمي صغير فقط بسبب الشجرة. أما استهلاك الذاكرة الكلي فهو
$$O(n+B+U)=O(n+U),$$
لأن \(B\le n\).