Fenwick träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 1 mars 2019; kontroller kräver 10 redigeringar .

Fenwick tree ( binary indexed tree , engelska  Fenwick tree, binary indexed tree , BIT) är en datastruktur som låter dig snabbt ändra värden i en matris och hitta några funktioner från matriselement. Först beskrevs av Ryabko B.Ya. år 1989. [1] Full version publicerad av honom på engelska 1992. [2]

Två år senare (1994) dök en artikel av P. Fenwick [3] upp , där samma struktur beskrevs, senare kallad "Fenwick-trädet".

Fenwick träd för summan

För ett naturligt tal kommer vi att beteckna den maximala divisorn , som är en potens av två (vi anser också att enheten är en potens av två). Det är lätt att se att F ( n )= n −( n  & ( n − 1)), där & är bitvis OCH av två heltal. Låt vår array ha element: . Vi väljer för vilket . Sedan, för att lagra Fenwick-trädet, behöver du en rad element . Vi kommer att numrera dem från 1 till . Cellen kommer att lagra summan i cellerna i arrayen från till .

Fenwick-trädet för summan stöder 2 operationer:

1) modifiera med argument och  — ändra värdet på den -th cellen i arrayen till ett tal ( det kan vara antingen positivt eller negativt).

2) räkna med ett argument  - hitta summan av siffror i cellerna i arrayen från 1:a till th.

Båda operationerna kan enkelt implementeras i en cykel.

modifiera(N,X)

ett) i=N
2) Medan i≤
2.1)    Öka b[i] med X
2.2)    Öka i med F(i)


räkna(N)

1) res=0

2) i=N

3) Hejdå

3.1) Öka res med b[i]

3.2) Minska i med F(i)

4) Svar = res

Komplexiteten för båda operationerna är O(k) = O(log n). Det är värt att notera att med hjälp av count(N)-operationen kan vi generellt hitta summan på vilket segment som helst för samma komplexitet, eftersom det för ≠1 är exakt lika med .

Fenwick träd för maximal

Fenwick-trädet för maximalt stöder följande operationer:

1) modifiera med argument och  — om värdet i den :e cellen i arrayen är mindre än , skriv sedan ett tal till den . Lämna annars värdet som det är.

2) räkna med argument och  - hitta det maximala antalet i cellerna i arrayen från -th till -th.

För att lagra trädet kommer vi , förutom arrayen , att använda arrayer och . I den e cellen i arrayen kommer vi att lagra maximum på segmentet ; i arrayens :e cell  - det maximala på segmentet vid och på segmentet vid .

Nedan följer genomförandet av verksamheten.

modifiera(N,X)

1)a[N]=max(a[N],X)

2)i=N

3) Hejdå

3.1)vänster[i]=max(vänster[i],X)

3.2) Öka i med F(i)

4)j=N

5) Hejdå

5.1)höger[j]=max(höger[j],X)

5.2) Minska j med F(j)

räkna(L,R)

1)res=0

2)i=L

3) Hejdå

3.1)res=max(res,höger[i])

3.2) Öka i med F(i)

4)res=max(res,a[i])

5)j=R

6) Hejdå

6.1)res=max(res,vänster[j])

6.2) Minska j med F(j)

7) Svar = res

Operationernas komplexitet = .

Observera att om du använder Fenwick-trädet som maximum kan du inte minska värdet som registreras i cellen. Om du vill att din datastruktur ska ha denna förmåga, bör du använda ett skärningsträd för maximalt.

Operationerna kan enkelt modifieras så att Fenwick-trädet hittar inte bara värdet av maximivärdet, utan även cellen där detta maximum uppnås.

Anteckningar

  1. ↑ Boris Ryabko. Snabb sekventiell kod.  // Rapporter från USSR:s vetenskapsakademi  : tidskrift. - 1989. - T. 306 , nr 3 . - S. 548-552 .
  2. ↑ Boris Ryabko. En snabb on-line adaptiv kod  (engelska)  // IEEE Trans.on Inform.Theory. - 1992. - Vol. 28 , nr. 1 . - P. 1400-1404 .
  3. ↑ Peter M. Fenwick. En ny datastruktur för kumulativa frekvenstabeller  //  Software: Practice and Experience: journal. - 1994. - Vol. 24 , nr. 3 . - s. 327-336 . - doi : 10.1002/spe.4380240306 .

Länkar