Fenwick træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. marts 2019; checks kræver 10 redigeringer .

Fenwick tree ( binært indekseret træ , engelsk  Fenwick træ, binært indekseret træ , BIT) er en datastruktur, der giver dig mulighed for hurtigt at ændre værdier i et array og finde nogle funktioner fra array-elementer. Først beskrevet af Ryabko B.Ya. i 1989. [1] Fuld version udgivet af ham på engelsk i 1992. [2]

To år senere (i 1994) udkom en artikel af P. Fenwick [3] , hvor den samme struktur blev beskrevet, senere kaldet "Fenwick-træet".

Fenwick træ for summen

For et naturligt tal vil vi betegne den maksimale divisor , som er en potens af to (vi betragter også enheden som en potens af to). Det er let at se, at F ( n )= n −( n  & ( n − 1)), hvor & er bitvis OG af to heltal. Lad vores array have elementer: . Vi vælger til hvilken . Derefter, for at opbevare Fenwick-træet, har du brug for en række elementer . Vi nummererer dem fra 1 til . Cellen vil gemme summen i cellerne i arrayet fra til .

Fenwick-træet for summen understøtter 2 operationer:

1) modificere med argumenter og  — ændre værdien af ​​den -th celle i arrayet til et tal ( det kan være enten positivt eller negativt).

2) tæl med et argument  - find summen af ​​tal i cellerne i arrayet fra 1. til th.

Begge operationer kan nemt implementeres i én cyklus.

modificere(N,X)

en) i=N
2) Mens i≤
2.1)    Forøg b[i] med X
2.2)    Forøg i med F(i)


antal (N)

1) res=0

2) i=N

3) Farvel

3.1) Forøg res med b[i]

3.2) Reducer i med F(i)

4) Svar = res

Kompleksiteten af ​​begge operationer er O(k) = O(log n). Det er værd at bemærke, at ved hjælp af count(N) operationen kan vi generelt finde summen på ethvert segment for samme kompleksitet, da det for ≠1 er nøjagtigt lig med .

Fenwick træ for maksimalt

Fenwick-træet for maksimal understøtter følgende operationer:

1) modificer med argumenter og  — hvis værdien i den th celle i arrayet er mindre end , så skriv et tal til den . Ellers lad værdien være som den er.

2) tæl med argumenter og  - find det maksimale antal i cellerne i arrayet fra -th til -th.

For at gemme træet vil vi ud over arrayet bruge arrays og . I den th celle i arrayet vil vi gemme maksimum på segmentet ; i den th celle i arrayet  - maksimum på segmentet ved og på segmentet ved .

Følgende er gennemførelsen af ​​operationerne.

modificere(N,X)

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

2)i=N

3) Farvel

3.1)venstre[i]=max(venstre[i],X)

3.2) Forøg i med F(i)

4)j=N

5) Farvel

5.1)højre[j]=max(højre[j],X)

5.2) Formindsk j med F(j)

tælle(L,R)

1)res=0

2)i=L

3) Farvel

3.1)res=max(res,right[i])

3.2) Forøg i med F(i)

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

5)j=R

6) Farvel

6.1)res=max(res,venstre[j])

6.2) Formindsk j med F(j)

7) Svar = res

Kompleksitet af operationer = .

Bemærk, at hvis du bruger Fenwick-træet som maksimum, kan du ikke reducere værdien, der er registreret i cellen. Hvis du ønsker, at din datastruktur skal have denne funktion, bør du maksimalt bruge et udskæringstræ .

Operationerne kan nemt ændres, så Fenwick-træet finder ikke kun værdien af ​​maksimum, men også cellen, hvor dette maksimum er nået.

Noter

  1. ↑ Boris Ryabko. Hurtig sekventiel kode.  // Rapporter fra Videnskabsakademiet i USSR  : tidsskrift. - 1989. - T. 306 , nr. 3 . - S. 548-552 .
  2. ↑ Boris Ryabko. En hurtig online adaptiv kode  (engelsk)  // IEEE Trans.on Inform.Theory. - 1992. - Bd. 28 , nr. 1 . - S. 1400-1404 .
  3. ↑ Peter M. Fenwick. En ny datastruktur for kumulative frekvenstabeller  //  Software: Practice and Experience: journal. - 1994. - Bd. 24 , nr. 3 . - s. 327-336 . - doi : 10.1002/spe.4380240306 .

Links