Let \(C(n)\) be the number of intervals \(I=[l,r]\subseteq [1,n]\) for which the values \(\mu(k)=1\) and \(\mu(k)=-1\) stay in almost perfect balance. If we write
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\},$$
then the counted intervals are exactly those satisfying
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Values with \(\mu(k)=0\) are neutral: they lengthen the interval but do not change either count. The implementations verify the derivation with
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
and then evaluate the same method at \(n=20000000\).
The key reduction is to replace interval counting by a pair-counting problem on weighted prefix sums.
We need \(\mu(1),\mu(2),\dots,\mu(n)\). The Möbius function takes the values
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ is a product of }t\text{ distinct primes},\\ 0, & m\text{ is divisible by }p^2\text{ for some prime }p. \end{cases}$$
The implementations build these values with a linear sieve, so the preprocessing is essentially one forward pass through the integers.
For an interval \(I=[l,r]\), define
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
The interval is counted precisely when neither sign dominates the other by more than the factor \(100/99\):
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
This formulation makes clear that entries with \(\mu(k)=0\) do not affect the balance at all. In particular, an interval containing only zeros is valid because then \(P_I=N_I=0\).
Instead of counting good intervals directly, count the two ways an interval can fail:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
These two families are disjoint. Indeed, if both inequalities held, then adding them would give
$$-(P_I+N_I)\gt 0,$$
which is impossible. Therefore
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
The total number of intervals appears because there are \(n(n+1)/2\) choices of \([l,r]\subseteq [1,n]\).
Define two weight systems:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
Now define prefix sums
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
For an interval \(I=[l,r]\),
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
So
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
This converts interval counting into the problem of counting ordered pairs \((i,j)\) with \(0\le i\lt j\le n\) and a strict prefix inequality.
For the first bad family we must count
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
and similarly
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
Scanning the prefixes from left to right, we only need to know how many earlier prefix values are strictly smaller than the current one. A Fenwick tree supports exactly this operation after the prefix values are shifted into a dense range or compressed into sorted coordinates.
Hence the full problem becomes a pair of standard order-statistics passes over two prefix arrays.
The Möbius values are
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
Some representative intervals are easy to classify:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
so \([1,1]\in\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
so \([2,3]\in\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
hence both balance inequalities hold and \([1,2]\) is counted. Also \([8,9]\) contains only zeros, so \(P_I=N_I=0\) and it is counted as well.
For the first weight system, the prefix sums are
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
and for the second they are
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
The number of increasing pairs in the first sequence is \(6\), and in the second sequence it is \(36\). Since the total number of intervals is
$$\frac{10\cdot 11}{2}=55,$$
we obtain
$$C(10)=55-6-36=13,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same pipeline. First they compute the Möbius values up to \(n\) with a linear sieve. Then they run the interval-counting routine twice: once with weights \((99,-100)\) and once with weights \((-100,99)\). In each pass they build the weighted prefix sums, map those prefix values to Fenwick-tree indices, and accumulate how many earlier prefixes are strictly smaller than the current prefix. After obtaining the two bad counts, they subtract them from \(n(n+1)/2\).
The C++ and Java implementations also include a coordinate-compression fallback when the raw prefix-value span would make a dense Fenwick tree unnecessarily large. The mathematical quantity being counted is the same in every language.
Computing all Möbius values up to \(n\) by linear sieve costs \(O(n)\) time and \(O(n)\) memory. Each weighted pass constructs one prefix array in \(O(n)\) time and performs Fenwick queries and updates in \(O(n\log n)\) time in the worst case; when the prefix span is already dense, the logarithm is taken over that span instead of over the number of distinct compressed values. Therefore the overall method runs in \(O(n\log n)\) time with \(O(n)\) memory, a dramatic improvement over naive \(O(n^2)\) interval enumeration.
Sei \(C(n)\) die Anzahl der Intervalle \(I=[l,r]\subseteq [1,n]\), in denen die Werte \(\mu(k)=1\) und \(\mu(k)=-1\) fast perfekt ausbalanciert sind. Mit
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}$$
werden genau die Intervalle gezählt, für die
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I$$
gilt. Werte mit \(\mu(k)=0\) sind neutral: Sie verlängern das Intervall, ändern aber keinen der beiden Zähler. Die Implementierungen prüfen die Herleitung mit
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
und werten dieselbe Methode anschließend für \(n=20000000\) aus.
Die entscheidende Umformung besteht darin, Intervallzählung auf das Zählen von Paaren in gewichteten Präfixsummen zurückzuführen.
Benötigt werden \(\mu(1),\mu(2),\dots,\mu(n)\). Die Möbius-Funktion ist durch
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ ist Produkt von }t\text{ verschiedenen Primzahlen},\\ 0, & m\text{ ist durch }p^2\text{ für ein Prime }p\text{ teilbar} \end{cases}$$
gegeben. Die Implementierungen berechnen diese Werte mit einem linearen Sieb, also mit nahezu einem einzigen Vorwärtsdurchlauf.
Für ein Intervall \(I=[l,r]\) definieren wir
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
Das Intervall wird genau dann gezählt, wenn keines der beiden Vorzeichen das andere um mehr als den Faktor \(100/99\) überwiegt:
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Damit ist sofort klar, dass Terme mit \(\mu(k)=0\) das Gleichgewicht nicht beeinflussen. Ein Intervall, das nur aus Nullen besteht, ist also zulässig, weil dann \(P_I=N_I=0\) gilt.
Statt gute Intervalle direkt zu zählen, zählen wir die beiden Arten des Scheiterns:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
Diese beiden Familien sind disjunkt. Würden beide Ungleichungen gleichzeitig gelten, so ergäbe ihre Summe
$$-(P_I+N_I)\gt 0,$$
was unmöglich ist. Also gilt
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
Der Term \(n(n+1)/2\) ist die Gesamtzahl aller Intervalle \([l,r]\subseteq [1,n]\).
Definiere zwei Gewichtungen:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
Dazu kommen die Präfixsummen
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
Für \(I=[l,r]\) gilt dann
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
Somit folgt
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
Damit ist die Intervallaufgabe auf das Zählen geordneter Paare \((i,j)\) mit \(0\le i\lt j\le n\) und strenger Präfix-Ungleichung reduziert.
Für die erste schlechte Familie müssen wir
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\}$$
berechnen, und analog
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
Beim Links-nach-rechts-Scan der Präfixe braucht man also nur die Anzahl der früheren Präfixwerte, die strikt kleiner als der aktuelle sind. Ein Fenwick-Baum unterstützt genau diese Abfrage, sobald die Präfixwerte in einen dichten Indexbereich verschoben oder auf sortierte Koordinaten komprimiert wurden.
Die Möbius-Werte lauten
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
Einige Intervalle lassen sich direkt klassifizieren:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
also liegt \([1,1]\) in \(\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
also liegt \([2,3]\) in \(\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
daher sind beide Balance-Ungleichungen erfüllt und \([1,2]\) wird gezählt. Ebenso enthält \([8,9]\) nur Nullen, also \(P_I=N_I=0\), und ist ebenfalls zulässig.
Für die erste Gewichtung erhält man die Präfixsummen
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
für die zweite
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
Die erste Folge besitzt \(6\) wachsende Paare, die zweite \(36\). Da es insgesamt
$$\frac{10\cdot 11}{2}=55$$
Intervalle gibt, folgt
$$C(10)=55-6-36=13,$$
genau wie im Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline. Zuerst werden die Möbius-Werte bis \(n\) mit einem linearen Sieb berechnet. Danach läuft die Intervallzählung zweimal: einmal mit den Gewichten \((99,-100)\) und einmal mit \((-100,99)\). In jedem Durchlauf entstehen gewichtete Präfixsummen; diese Präfixwerte werden in Fenwick-Indizes überführt, und dann wird aufaddiert, wie viele frühere Präfixe strikt kleiner als das aktuelle sind. Sind beide schlechten Anzahlen bekannt, werden sie von \(n(n+1)/2\) subtrahiert.
Die C++- und Java-Implementierungen besitzen zusätzlich einen Fallback mit Koordinatenkompression, falls die rohe Spannweite der Präfixwerte einen dichten Fenwick-Baum unnötig groß machen würde. Die gezählte mathematische Größe bleibt in allen Sprachen identisch.
Die Berechnung aller Möbius-Werte bis \(n\) mittels linearem Sieb kostet \(O(n)\) Zeit und \(O(n)\) Speicher. Jeder gewichtete Durchlauf baut ein Präfixarray in \(O(n)\) Zeit auf und führt Fenwick-Abfragen sowie Updates im schlechtesten Fall in \(O(n\log n)\) Zeit aus; bei bereits dichter Präfixspanne bezieht sich der Logarithmus auf diese Spannweite statt auf die Anzahl komprimierter Werte. Insgesamt erhält man also \(O(n\log n)\) Zeit und \(O(n)\) Speicher statt naiver \(O(n^2)\)-Enumeration.
\(C(n)\), \([1,n]\) içindeki \(I=[l,r]\) aralıklarından, \(\mu(k)=1\) ve \(\mu(k)=-1\) değerlerinin neredeyse kusursuz dengede kaldığı aralıkların sayısını göstersin. Eğer
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}$$
dersek, sayılan aralıklar tam olarak
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I$$
koşullarını sağlar. \(\mu(k)=0\) olan terimler nötrdür: aralığın uzunluğunu artırırlar ama iki sayacı değiştirmezler. Uygulamalar şu kontrol değerlerini doğrular:
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
ve ardından aynı yöntemi \(n=20000000\) için uygular.
Temel fikir, aralık sayımını ağırlıklı prefix toplamlar üzerindeki ikili karşılaştırma problemine dönüştürmektir.
\(\mu(1),\mu(2),\dots,\mu(n)\) değerlerine ihtiyacımız var. Möbius fonksiyonu
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ birbirinden farklı }t\text{ asalın çarpımıysa},\\ 0, & m\text{ bir }p^2\text{ karesel asal çarpanına sahipse} \end{cases}$$
şeklindedir. Uygulamalar bu değerleri lineer sieve ile hesaplar; yani ön işleme yaklaşık tek bir ileri taramadır.
Bir \(I=[l,r]\) aralığı için
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}$$
tanımını yapalım. Aralık ancak ve ancak iki işaretten biri diğerine \(100/99\) oranından daha fazla üstün gelmiyorsa sayılır:
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Böylece \(\mu(k)=0\) olanların dengeyi hiç etkilemediği açıkça görülür. Özellikle yalnızca sıfırlardan oluşan bir aralık geçerlidir; çünkü o durumda \(P_I=N_I=0\) olur.
İyi aralıkları doğrudan saymak yerine, başarısız olmanın iki yolunu saymak daha kolaydır:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
Bu iki aile ayrık kümelerdir. Eğer iki eşitsizlik de aynı anda doğru olsaydı, toplandıklarında
$$-(P_I+N_I)\gt 0$$
elde edilirdi; bu ise imkansızdır. Dolayısıyla
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
Buradaki \(n(n+1)/2\), \([1,n]\) içindeki tüm aralıkların toplam sayısıdır.
İki ağırlık sistemi tanımlayalım:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
Ardından prefix toplamları kurarız:
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
O zaman \(I=[l,r]\) için
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I$$
olur. Yani
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
Böylece aralık sayımı, \(0\le i\lt j\le n\) ve sıkı prefix eşitsizliği sağlayan sıralı çiftleri saymaya dönüşür.
Birinci kötü aile için saymamız gereken miktar
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
ikincisi için de
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}$$
şeklindedir. Prefixler soldan sağa taranırken gereken tek bilgi, o ana kadar görülen prefix değerleri arasında mevcut değerden küçük kaç tane olduğudur. Fenwick ağacı bu sorguyu, prefix değerleri kaydırılmış ya da sıralı koordinatlara sıkıştırılmış indekslere dönüştürüldükten sonra verimli biçimde yapar.
Möbius değerleri
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1)$$
olur. Bazı aralıkları doğrudan sınıflandırabiliriz:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
yani \([1,1]\in\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
yani \([2,3]\in\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
bu yüzden iki denge eşitsizliği de sağlanır ve \([1,2]\) sayılır. Ayrıca \([8,9]\) yalnızca sıfırlardan oluştuğu için \(P_I=N_I=0\) olur ve o da geçerlidir.
Birinci ağırlık sistemi için prefix toplamları
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
ikinci sistem için ise
$$B=(0,-100,-1,98,98,197,97,196,196,196,96)$$
şeklindedir. Birinci dizide \(6\), ikinci dizide \(36\) artan çift vardır. Toplam aralık sayısı
$$\frac{10\cdot 11}{2}=55$$
olduğundan
$$C(10)=55-6-36=13$$
elde edilir; bu da kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce Möbius değerleri lineer sieve ile \(n\)'ye kadar üretilir. Sonra aralık sayım yordamı iki kez çalıştırılır: bir kez \((99,-100)\), bir kez de \((-100,99)\) ağırlıklarıyla. Her geçişte ağırlıklı prefix toplamları oluşturulur, bu değerler Fenwick ağacında kullanılacak indekslere dönüştürülür ve önceki prefixlerden kaç tanesinin mevcut prefixten küçük olduğu toplanır. Son adımda iki kötü sayım \(n(n+1)/2\)'den çıkarılır.
C++ ve Java uygulamaları ayrıca, prefix değerlerinin ham aralığı çok büyürse koordinat sıkıştırmasına geçer. Sayılan matematiksel nesne bütün dillerde aynıdır.
Möbius değerlerini lineer sieve ile üretmek \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Her ağırlıklı geçiş \(O(n)\) sürede bir prefix dizisi kurar ve en kötü durumda Fenwick sorguları ile güncellemeleri \(O(n\log n)\) zamanda yapar; eğer prefix aralığı zaten sıkı ve yoğunsa logaritma, sıkıştırılmış değer sayısı yerine bu aralığa göre alınır. Sonuç olarak toplam maliyet \(O(n\log n)\), bellek kullanımı \(O(n)\) olur; bu da saf \(O(n^2)\) aralık taramasına göre çok daha iyidir.
Sea \(C(n)\) el número de intervalos \(I=[l,r]\subseteq [1,n]\) en los que los valores \(\mu(k)=1\) y \(\mu(k)=-1\) permanecen casi perfectamente equilibrados. Si definimos
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\},$$
entonces los intervalos contados son exactamente los que cumplen
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Los valores con \(\mu(k)=0\) son neutros: alargan el intervalo pero no modifican ninguno de los dos conteos. Las implementaciones verifican la derivación con
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
y después aplican el mismo método para \(n=20000000\).
La reducción central consiste en transformar el conteo de intervalos en un conteo de pares sobre prefijos ponderados.
Necesitamos \(\mu(1),\mu(2),\dots,\mu(n)\). La función de Möbius toma los valores
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ es producto de }t\text{ primos distintos},\\ 0, & m\text{ es divisible por }p^2\text{ para algún primo }p. \end{cases}$$
Las implementaciones construyen esta tabla con una criba lineal, así que el preprocesamiento es esencialmente una sola pasada ascendente.
Para un intervalo \(I=[l,r]\), definimos
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
El intervalo se cuenta si ninguno de los dos signos supera al otro por un factor mayor que \(100/99\):
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Así se ve inmediatamente que los términos con \(\mu(k)=0\) no afectan al equilibrio. En particular, un intervalo formado solo por ceros es válido porque entonces \(P_I=N_I=0\).
En vez de contar directamente los intervalos buenos, contamos las dos maneras de fallar:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
Estas familias son disjuntas. Si ambas desigualdades fueran ciertas a la vez, al sumarlas obtendríamos
$$-(P_I+N_I)\gt 0,$$
lo cual es imposible. Por tanto,
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
El término \(n(n+1)/2\) es simplemente el número total de intervalos \([l,r]\subseteq [1,n]\).
Definimos dos sistemas de pesos:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
Luego construimos los prefijos
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
Para un intervalo \(I=[l,r]\), se cumple
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
De ahí se deduce que
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
De este modo, el conteo de intervalos queda reducido al conteo de pares ordenados \((i,j)\) con \(0\le i\lt j\le n\) y una desigualdad estricta entre prefijos.
Para la primera familia mala debemos calcular
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
y de forma análoga
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
Al recorrer los prefijos de izquierda a derecha, solo hace falta saber cuántos prefijos anteriores son estrictamente menores que el actual. Un árbol Fenwick resuelve exactamente esa consulta una vez que los valores de los prefijos se desplazan a un rango denso o se comprimen por coordenadas.
Los valores de Möbius son
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
Algunos intervalos representativos son:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
así que \([1,1]\in\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
de modo que \([2,3]\in\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
por lo que ambas desigualdades de equilibrio se satisfacen y \([1,2]\) se cuenta. Además, \([8,9]\) contiene solo ceros, de modo que \(P_I=N_I=0\) y también es válido.
Para el primer sistema de pesos, los prefijos son
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
y para el segundo
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
La primera sucesión tiene \(6\) pares crecientes y la segunda \(36\). Como el número total de intervalos es
$$\frac{10\cdot 11}{2}=55,$$
obtenemos
$$C(10)=55-6-36=13,$$
exactamente el valor de control usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma tubería. Primero calculan los valores de Möbius hasta \(n\) con una criba lineal. Después ejecutan dos veces la rutina de conteo de intervalos: una con pesos \((99,-100)\) y otra con \((-100,99)\). En cada pasada construyen los prefijos ponderados, convierten esos valores en índices para un árbol Fenwick y acumulan cuántos prefijos anteriores son estrictamente menores que el prefijo actual. Una vez conocidas las dos cantidades malas, se restan de \(n(n+1)/2\).
Las versiones en C++ y Java además cambian a compresión de coordenadas cuando el rango bruto de los prefijos haría demasiado grande un Fenwick denso. La cantidad matemática contada es la misma en los tres lenguajes.
Generar todos los valores de Möbius hasta \(n\) con criba lineal cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Cada pasada ponderada construye un arreglo de prefijos en \(O(n)\) y realiza consultas y actualizaciones Fenwick en \(O(n\log n)\) en el peor caso; si el rango de prefijos ya es denso, el logaritmo se toma sobre ese rango en lugar de sobre el número de valores comprimidos. En conjunto, el método tarda \(O(n\log n)\) y usa \(O(n)\) memoria, muy por debajo de la enumeración ingenua \(O(n^2)\).
记 \(C(n)\) 为所有区间 \(I=[l,r]\subseteq [1,n]\) 中，\(\mu(k)=1\) 与 \(\mu(k)=-1\) 两类值保持近乎完全平衡的区间个数。若定义
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\},$$
那么被计入答案的区间恰好满足
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
\(\mu(k)=0\) 的项是中性的：它们会延长区间长度，但不会改变这两个计数。因此实现实际上是在全部区间中，筛出正负两类 Möbius 值比例足够接近的那些区间。程序先用
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319$$
这三个检查点验证推导，然后再把同一算法用于 \(n=20000000\)。
核心思路是把“统计满足条件的区间”改写成“统计前缀和中满足严格大小关系的有序对”。
我们需要 \(\mu(1),\mu(2),\dots,\mu(n)\)。Möbius 函数满足
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ 是 }t\text{ 个互异素数的乘积},\\ 0, & m\text{ 含有某个素数的平方因子 }p^2. \end{cases}$$
实现采用线性筛生成这张表，因此预处理本质上是一趟从小到大的扫描。这里的重点不是单独分析某个区间，而是先把整个 \([1,n]\) 上的 \(\mu\) 序列一次性准备好。
对任意区间 \(I=[l,r]\)，定义
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
题目要求保留下来的区间，就是这两个数量非常接近的区间。代码对应的判定条件是
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
这说明任何一边都不能比另一边大出超过 \(100/99\) 的倍数。由于 \(\mu(k)=0\) 完全不出现在这两个式子里，所以它们对平衡条件没有贡献。特别地，如果某个区间里全是零，那么 \(P_I=N_I=0\)，这个区间也应被计入答案。
直接数好区间并不方便，但数坏区间很自然。定义
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
\(\mathcal{A}\) 表示 \(\mu=1\) 一侧明显偏多，\(\mathcal{B}\) 表示 \(\mu=-1\) 一侧明显偏多。这两个坏集合是互不相交的。因为如果一个区间同时满足两条严格不等式，那么相加就会得到
$$-(P_I+N_I)\gt 0,$$
这是不可能的。于是可以直接写出
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
这里 \(\frac{n(n+1)}{2}\) 是 \([1,n]\) 中全部区间的总数。问题已经被拆成两个彼此独立的坏区间计数。
为两类坏区间分别定义权重函数：
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
再定义前缀和
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
对于区间 \(I=[l,r]\)，由前缀和差分可得
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
因此
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
原来的区间问题就被压缩成：统计多少对下标 \((i,j)\) 满足 \(0\le i\lt j\le n\)，并且当前前缀值严格大于之前的前缀值。
于是我们需要计算
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
以及
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
从左到右扫描前缀时，对每个当前位置 \(j\)，只要知道此前出现过多少个更小的前缀值即可。这正是 Fenwick 树擅长的事情。若前缀值范围较小，可以直接平移到一个稠密整数区间；若范围较大，则先做坐标压缩，再在压缩后的下标上维护频数。数学上无论采用哪种映射，统计到的都是同一批严格递增前缀对。
先写出 Möbius 值：
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
几个区间可以直接看出分类结果：
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
所以 \([1,1]\in\mathcal{A}\)。
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
所以 \([2,3]\in\mathcal{B}\)。
$$[1,2]:\ P_I=1,\ N_I=1,$$
两条平衡不等式都成立，因此 \([1,2]\) 是好区间。再比如 \([8,9]\) 只有零值，所以 \(P_I=N_I=0\)，它也应该被计入。
对第一组权重，前缀和序列为
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
对第二组权重，前缀和序列为
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
第一列前缀里一共有 \(6\) 个严格递增有序对，第二列里有 \(36\) 个。全部区间总数是
$$\frac{10\cdot 11}{2}=55,$$
于是
$$C(10)=55-6-36=13,$$
正好和检查点一致。
C++、Python 和 Java 实现遵循完全相同的主线。第一步，用线性筛生成 \(1\) 到 \(n\) 的 Möbius 值。第二步，分别对权重 \((99,-100)\) 与 \((-100,99)\) 做两次扫描。每次扫描都构造加权前缀和，并把这些前缀值映射到 Fenwick 树的下标上，然后累计“此前出现过多少个更小的前缀值”。这两个数量分别就是两类坏区间的个数，最后用总区间数 \(n(n+1)/2\) 减掉它们即可。
C++ 和 Java 版本还会在前缀值跨度过大时切换到坐标压缩；Python 版本保留了直接按前缀跨度建立索引的写法。无论索引方式如何变化，统计对象始终是同一个前缀有序对问题。
线性筛求 Möbius 表需要 \(O(n)\) 时间和 \(O(n)\) 空间。每一次加权扫描都先在 \(O(n)\) 时间内构造前缀数组，再通过 Fenwick 树完成 \(O(n\log n)\) 级别的查询与更新；如果采用的是稠密下标，那么对数因子对应的是前缀值跨度，但仍然被 \(O(\log n)\) 控制。于是总复杂度为 \(O(n\log n)\)，空间复杂度为 \(O(n)\)，远优于朴素的 \(O(n^2)\) 区间枚举。
Пусть \(C(n)\) обозначает число интервалов \(I=[l,r]\subseteq [1,n]\), в которых значения \(\mu(k)=1\) и \(\mu(k)=-1\) находятся почти в идеальном равновесии. Если ввести
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\},$$
то в ответ входят ровно те интервалы, для которых выполнено
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Значения \(\mu(k)=0\) нейтральны: они расширяют интервал, но не изменяют ни один из счетчиков. Реализации проверяют вывод на значениях
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
после чего применяют тот же алгоритм к \(n=20000000\).
Ключевая идея состоит в том, чтобы заменить подсчет интервалов подсчетом пар на взвешенных префиксных суммах.
Нужны значения \(\mu(1),\mu(2),\dots,\mu(n)\). Функция Мёбиуса задается так:
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m\text{ есть произведение }t\text{ различных простых},\\ 0, & m\text{ делится на }p^2\text{ для некоторого простого }p. \end{cases}$$
Во всех реализациях эта таблица строится линейным решетом, поэтому предварительный этап представляет собой практически один проход по числам от \(1\) до \(n\).
Для интервала \(I=[l,r]\) определим
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
Интервал засчитывается тогда и только тогда, когда ни один из знаков не превосходит другой больше чем в \(100/99\) раза:
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
Из этой записи сразу видно, что элементы с \(\mu(k)=0\) на баланс не влияют. В частности, интервал, состоящий только из нулей, допустим, потому что тогда \(P_I=N_I=0\).
Вместо прямого подсчета хороших интервалов удобно считать два способа нарушения условия:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
Эти два семейства не пересекаются. Если бы обе строгие неравенства выполнялись одновременно, их сумма дала бы
$$-(P_I+N_I)\gt 0,$$
что невозможно. Следовательно,
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
Здесь \(\frac{n(n+1)}{2}\) есть общее число интервалов \([l,r]\subseteq [1,n]\).
Введем две весовые функции:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
Теперь зададим префиксные суммы
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
Тогда для \(I=[l,r]\)
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
Отсюда следует
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
Итак, задача о интервалах свелась к подсчету упорядоченных пар \((i,j)\) с \(0\le i\lt j\le n\), для которых выполнено строгое сравнение между двумя префиксами.
Для первого плохого семейства нужно вычислить
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
а для второго аналогично
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
Если сканировать префиксы слева направо, для каждого текущего значения нужно знать лишь, сколько более ранних префиксов строго меньше него. Это эффективно поддерживается деревом Фенвика после сдвига значений в плотный диапазон индексов или после координатного сжатия.
Значения функции Мёбиуса равны
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
Некоторые интервалы классифицируются сразу:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
поэтому \([1,1]\in\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
поэтому \([2,3]\in\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
обе неравенства баланса выполняются, и \([1,2]\) учитывается. Кроме того, \([8,9]\) состоит только из нулей, значит \(P_I=N_I=0\), и этот интервал тоже допустим.
Для первой системы весов префиксы равны
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
для второй системы
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
В первой последовательности имеется \(6\) возрастающих пар, во второй \(36\). Общее число интервалов равно
$$\frac{10\cdot 11}{2}=55,$$
поэтому
$$C(10)=55-6-36=13,$$
что совпадает с контрольным значением в реализациях.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала линейным решетом строятся значения функции Мёбиуса до \(n\). Затем процедура подсчета интервалов выполняется дважды: один раз с весами \((99,-100)\), второй раз с весами \((-100,99)\). На каждом проходе формируются взвешенные префиксные суммы, эти значения преобразуются в индексы дерева Фенвика, и накапливается число предыдущих префиксов, которые строго меньше текущего. После получения двух плохих количеств они вычитаются из \(n(n+1)/2\).
Версии на C++ и Java дополнительно используют координатное сжатие, если сырой диапазон префиксов сделал бы плотную структуру слишком большой. С математической точки зрения во всех языках считается одна и та же величина.
Построение всех значений функции Мёбиуса до \(n\) линейным решетом занимает \(O(n)\) времени и \(O(n)\) памяти. Каждый взвешенный проход строит массив префиксов за \(O(n)\) и выполняет запросы и обновления в дереве Фенвика за \(O(n\log n)\) в худшем случае; если диапазон префиксов уже плотный, логарифм берется по этому диапазону, но асимптотика остается той же. В итоге получается \(O(n\log n)\) по времени и \(O(n)\) по памяти, что намного лучше наивного перебора всех \(O(n^2)\) интервалов.
لتكن \(C(n)\) هي عدد الفترات \(I=[l,r]\subseteq [1,n]\) التي تبقى فيها القيمتان \(\mu(k)=1\) و\(\mu(k)=-1\) في توازن شبه تام. إذا عرّفنا
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\},$$
فإن الفترات التي تدخل في الناتج هي بالضبط الفترات التي تحقق
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
القيم التي تحقق \(\mu(k)=0\) محايدة: فهي تزيد طول الفترة، لكنها لا تغيّر أيا من العدّين السابقين. تتحقق التطبيقات من صحة الاشتقاق باستعمال
$$C(10)=13,\qquad C(500)=16676,\qquad C(10000)=20155319,$$
ثم تطبق المنهج نفسه على \(n=20000000\).
الفكرة الأساسية هي استبدال عدّ الفترات مباشرة بمسألة عدّ أزواج مرتبة داخل مجاميع بادئة موزونة.
نحتاج إلى \(\mu(1),\mu(2),\dots,\mu(n)\). دالة Möbius تُعطى بالصيغة
$$\mu(m)=\begin{cases} 1, & m=1,\\ (-1)^t, & m = p_1p_2\cdots p_t \text{ with distinct primes},\\ 0, & p^2\mid m \text{ for some prime } p. \end{cases}$$
التنفيذات تبني هذه القيم بغربال خطي، ولذلك فإن مرحلة التمهيد هي في الجوهر مرور تصاعدي واحد على الأعداد.
لكل فترة \(I=[l,r]\) نعرّف
$$P_I=\#\{k\in I:\mu(k)=1\},\qquad N_I=\#\{k\in I:\mu(k)=-1\}.$$
وتُحسب الفترة إذا وفقط إذا لم يطغ أحد الإشارتين على الآخر بأكثر من العامل \(100/99\):
$$99P_I\le 100N_I,\qquad 99N_I\le 100P_I.$$
ومن هذه الصياغة يظهر مباشرة أن الحدود التي تحقق \(\mu(k)=0\) لا تؤثر في التوازن. ولهذا فإن الفترة التي تتكون من أصفار فقط تعدّ صالحة لأن \(P_I=N_I=0\).
بدلا من عدّ الفترات الجيدة مباشرة، نعدّ طريقتين فقط لفشل الشرط:
$$\mathcal{A}=\{I:99P_I-100N_I\gt 0\},\qquad \mathcal{B}=\{I:99N_I-100P_I\gt 0\}.$$
هاتان العائلتان منفصلتان تماما. فلو تحقق الشرطان الصارمان معا لكان مجموعهما
$$-(P_I+N_I)\gt 0,$$
وهذا مستحيل. لذلك نحصل على
$$C(n)=\frac{n(n+1)}{2}-\#\mathcal{A}-\#\mathcal{B}.$$
والحد \(\frac{n(n+1)}{2}\) هو ببساطة العدد الكلي للفترات داخل \([1,n]\).
نعرّف نظامي أوزان:
$$a(k)=\begin{cases} 99, & \mu(k)=1,\\ -100, & \mu(k)=-1,\\ 0, & \mu(k)=0, \end{cases}\qquad b(k)=\begin{cases} -100, & \mu(k)=1,\\ 99, & \mu(k)=-1,\\ 0, & \mu(k)=0. \end{cases}$$
ثم نكوّن المجاميع البادئة
$$A_j=\sum_{k=1}^{j}a(k),\qquad B_j=\sum_{k=1}^{j}b(k),\qquad A_0=B_0=0.$$
وبالنسبة للفترة \(I=[l,r]\) نجد
$$A_r-A_{l-1}=99P_I-100N_I,\qquad B_r-B_{l-1}=99N_I-100P_I.$$
إذن
$$I\in\mathcal{A}\iff A_r\gt A_{l-1},\qquad I\in\mathcal{B}\iff B_r\gt B_{l-1}.$$
وبذلك تتحول مسألة الفترات إلى عدّ الأزواج المرتبة \((i,j)\) حيث \(0\le i\lt j\le n\) وتكون قيمة البادئة الحالية أكبر من قيمة بادئة سابقة.
بالنسبة إلى العائلة السيئة الأولى نحتاج إلى
$$\#\mathcal{A}=\#\{(i,j):0\le i\lt j\le n,\ A_j\gt A_i\},$$
وبالمثل
$$\#\mathcal{B}=\#\{(i,j):0\le i\lt j\le n,\ B_j\gt B_i\}.$$
عند مسح القيم البادئة من اليسار إلى اليمين، يكفي أن نعرف كم عدد القيم السابقة الأصغر من القيمة الحالية على نحو صارم. شجرة Fenwick تدعم هذا الاستعلام بكفاءة بعد نقل قيم البوادئ إلى مجال كثيف من الفهارس أو بعد ضغط الإحداثيات.
قيم Möbius هي
$$\bigl(\mu(1),\dots,\mu(10)\bigr)=(1,-1,-1,0,-1,1,-1,0,0,1).$$
بعض الفترات يمكن تصنيفها مباشرة:
$$[1,1]:\ P_I=1,\ N_I=0\ \Rightarrow\ 99P_I-100N_I=99\gt 0,$$
إذًا \([1,1]\in\mathcal{A}\).
$$[2,3]:\ P_I=0,\ N_I=2\ \Rightarrow\ 99N_I-100P_I=198\gt 0,$$
إذًا \([2,3]\in\mathcal{B}\).
$$[1,2]:\ P_I=1,\ N_I=1,$$
فتتحقق متباينتا التوازن معًا، ولذلك تُحسب الفترة \([1,2]\). وكذلك الفترة \([8,9]\) تتكون من أصفار فقط، لذا \(P_I=N_I=0\) وهي صالحة أيضا.
في نظام الأوزان الأول تكون المجاميع البادئة
$$A=(0,99,-1,-101,-101,-201,-102,-202,-202,-202,-103),$$
وفي النظام الثاني
$$B=(0,-100,-1,98,98,197,97,196,196,196,96).$$
يحوي التسلسل الأول \(6\) أزواج متزايدة ويحوي الثاني \(36\) زوجا متزايدا. وبما أن العدد الكلي للفترات هو
$$\frac{10\cdot 11}{2}=55,$$
فإننا نحصل على
$$C(10)=55-6-36=13,$$
وهو تماما مقدار نقطة التحقق في التنفيذات.
تتبع التنفيذات في C++ وPython وJava المسار نفسه. أولا تُحسب قيم Möbius حتى \(n\) بواسطة غربال خطي. بعد ذلك تُشغَّل روتينة عدّ الفترات مرتين: مرة بالأوزان \((99,-100)\) ومرة بالأوزان \((-100,99)\). في كل مرور تُبنى المجاميع البادئة الموزونة، ثم تُحوَّل قيمها إلى فهارس لشجرة Fenwick، ثم يُجمع عدد القيم السابقة الأصغر من القيمة الحالية. بعد معرفة العدّين السيئين يُطرحان من \(n(n+1)/2\).
تستخدم نسختا C++ وJava أيضا ضغط الإحداثيات عندما يكون المجال الخام لقيم البوادئ كبيرا جدا بحيث يجعل بنية Fenwick الكثيفة غير عملية. أما الكمية الرياضية نفسها فتبقى واحدة في جميع اللغات.
حساب جميع قيم Möbius حتى \(n\) بواسطة غربال خطي يكلف \(O(n)\) زمنا و\(O(n)\) ذاكرة. وكل مرور موزون يبني مصفوفة البوادئ في \(O(n)\)، ثم ينفذ استعلامات وتحديثات شجرة Fenwick في \(O(n\log n)\) في أسوأ الأحوال؛ وإذا كان مجال القيم كثيفا أصلا فإن عامل اللوغاريتم يتعلق بهذا المجال، لكنه يبقى ضمن \(O(\log n)\). لذلك تكون الكلفة الكلية \(O(n\log n)\) مع \(O(n)\) ذاكرة، وهي أفضل بكثير من الفحص الساذج لجميع الفترات بتعقيد \(O(n^2)\).