Kann man in O (n) einen Fenwickbaum bauen?

Question

Fenwick tree ist eine Datenstruktur, die zwei Arten von Operationen erlaubt (Sie es mit mehr Operationen vermehren können):

• Punkt Update update(index, value)
• Präfixsumme query(index)

Beide Operationen sind in O(log(n)) wobei n die Größe eines Arrays ist. Ich habe keine Probleme zu verstehen, wie man beide Operationen und die Logik dahinter ausführt.

---

Meine Frage ist, wie kann ich einen Fenwick-Baum von einem Array initialisieren. Klar kann ich dies in O(nlog(n)) zu erreichen, durch den Aufruf n mal update(i, arr[i]), aber gibt es eine Möglichkeit, es in O(n) zu initialisieren.

---

Warum ich dies zu fragen, ob Wikipedia sagt, dass Sie in nlog(n) initialisieren kann? Weil der Artikel so rudimentär ist, dass ich nicht sicher bin, ob es die beste Komplexität ist, die man erreichen kann. Auch Parallelen mit naiver Haufen Schöpfung, die durch Bestücken der Halde eins nach dem anderen getan und kann in O(n) in O(nlog(n)) gegen Smart Heap Initialisierung erreicht werden gibt mir Hoffnung, dass etwas Ähnliches in Fenwick Baum erfolgen.

Answer 1

[EDIT: Ich hatte Dinge "upside-down" - jetzt behoben]

Ja. Schleife durch die n Array-Elemente in zunehmender Indexreihenfolge, immer Addieren der Summe nur auf den nächsten kleinsten Index, dass sie hinzugefügt werden sollen, anstatt auf alle von ihnen:

for i = 1 to n: 
    j = i + (i & -i)  # Finds next higher index that this value should contribute to 
    if j <= n: 
     x[j] += x[i] 

Dies funktioniert, weil, obwohl jeder Wert mehrere Bereich Summen trägt zu, nachdem die unterste Bereich Summe der Verarbeitung, dass der Wert beiträgt (die eigentlich erfordert keine „Verarbeitung“, da die Summe schon drin ist), wir müssen nicht mehr ihre eigene Identität halten - es sicher sein kann, verschmolzen mit allen anderen Werten, die zu den verbleibenden Bereichssummen beitragen.

TTBOMK dieser Algorithmus ist "neu" - aber dann habe ich nicht sehr schwer aussehen;)