Czy można zbudować drzewo Fenwick w O (n)?

Question

Fenwick tree jest strukturą danych, która pozwala na dwa rodzaje działalności (można rozszerzyć go więcej operacji):

• zmiana punkt update(index, value)
• suma prefiks query(index)

Obie operacje są w O(log(n)) gdzie n jest rozmiarem tablicy. Nie mam problemów ze zrozumieniem, jak wykonywać zarówno operacje, jak i logikę za nimi.

---

Moje pytanie brzmi: jak mogę zainicjować drzewo Fenwick z tablicy. Najwyraźniej mogę to osiągnąć w O(nlog(n)), wywołując n razy update(i, arr[i]), ale czy istnieje sposób, aby go zainicjować w O(n).

---

Dlaczego pytaniem to jeśli wikipedia mówi, że można zainicjować w nlog(n)? Ponieważ artykuł jest tak prymitywny, że nie jestem pewien, czy jest to najlepsza złożoność, jaką można osiągnąć. Również rysowanie paraleli z naiwnym tworzeniem sterty, które odbywa się poprzez zapełnianie sterty jeden po drugim i może być osiągnięte w O(nlog(n)) w porównaniu do inicjacji inteligentnego sterty w O(n) daje mi nadzieję, że coś podobnego można zrobić w drzewie Fenwicka.

Answer 1

[EDIT: Miałem rzeczy "do góry nogami" - Poprawiono teraz]

Tak. Pętli pozycji n tablicy w kolejności rosnącej indeksu, zawsze dodając sumę tylko do następnej najmniejszej indeksu należy dodać do nich, a nie dla wszystkich z nich:

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] 

To działa, bo chociaż każdej wartości przyczynia się do kilku sum, po przetworzeniu najniższej sumy, do której wartość się przyczynia (która w rzeczywistości nie wymaga "przetwarzania", ponieważ suma już tam jest), nie musimy już utrzymywać jej oddzielnej tożsamości - można ją bezpiecznie połączone z wszystkimi innymi wartościami, które przyczyniają się do pozostałych kwot zasięgu.

TTBOMK ten algorytm jest "nowy" - ale wtedy nie wyglądała bardzo ciężko;)