Fenwick träd

Fenwick-träd Binärt indexerat träd
Skapande av ett binärt indexerat träd för arrayen [1, 2, 3, 4, 5] genom elementvis infogning
Typ	träd
Uppfunnet	1989
Uppfunnet av	Boris Ryabko
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Plats O( n ) O( n ) Sök O(log n ) O(log n ) Föra in O(log n ) O(log n ) Radera På) På)

Ett Fenwick-träd eller binärt indexerat träd ( BIT) är en datastruktur som effektivt kan uppdatera element och beräkna prefixsummor i en taltabell.

Denna struktur föreslogs av Boris Ryabko 1989 med ytterligare en modifiering publicerad 1992. Den har senare blivit känd under namnet Fenwick-trädet efter Peter Fenwick, som beskrev denna struktur i sin artikel från 1994.

Jämfört med en platt array av tal uppnår Fenwick-trädet en mycket bättre balans mellan två operationer: elementuppdatering och prefixsummaberäkning. En platt array med $n$ tal kan antingen lagra elementen eller prefixsummorna. I det första fallet kräver beräkning av prefixsummor linjär tid; i det andra fallet kräver uppdatering av arrayelementen linjär tid (i båda fallen kan den andra operationen utföras i konstant tid). Fenwick-träd gör att båda operationerna kan utföras i ${\displaystyle O(\log n)}-$ tid. Detta uppnås genom att representera siffrorna som ett träd med $n+1$ noder där värdet för varje nod i trädet är prefixsumman för matrisen från indexet för föräldern (inklusive) upp till nodens index (exklusivt). Själva trädet är implicit och kan lagras som en array med $n$ nummer, med den implicita rotnoden utelämnad från arrayen. Trädstrukturen tillåter operationerna för elementhämtning, elementuppdatering, prefixsumma och intervallsumma att utföras med endast $O(\log n)$ nodåtkomster.

Motivering

Huvudartikel: Prefixsummor § Ansökningar

Med tanke på en tabell med element är det ibland önskvärt att beräkna den löpande summan av värden upp till varje index enligt någon associativ binär operation (addition på heltal är den absolut vanligaste). Fenwick-träd tillhandahåller en metod för att fråga den löpande summan vid vilket index som helst, förutom att tillåta ändringar i den underliggande värdetabellen och att alla ytterligare frågor återspeglar dessa ändringar.

Fenwick-träd är speciellt utformade för att implementera den aritmetiska kodningsalgoritmen , som upprätthåller räkningar av varje symbol som produceras och måste konvertera dessa till den kumulativa sannolikheten för en symbol som är mindre än en given symbol. Utvecklingen av verksamheten som stöds var i första hand motiverad av användning i det fallet.

Om man använder ett Fenwick-träd krävs bara $O(\log n)$ operationer för att beräkna vilken önskad kumulativ summa som helst, eller mer generellt summan av ett värdeintervall (som inte nödvändigtvis börjar på noll). Det är också möjligt att konstruera förlängningar av denna datastruktur för att snabbt beräkna kumulativa summor på $d$ -dimensionella arrayer i $O(\log ^{d}n)$ tid.

Beskrivning

Ett Fenwick-träd är lättast att förstå genom att betrakta en en-baserad array $A[n]$ med $n$ element. Motsvarande Fenwick-träd har $n+1$ noder med en implicit nod 0 vid roten. Varje nivå $k$ i trädet innehåller noder med index som motsvarar summan av $k$ distinkta potenser av 2 (med $k=0$ som representerar en tom summa 0). Till exempel, nivå $k=1$ innehåller noder $1=2^{0},2=2^{1},4=2^{2},...$ och nivå $k=2$ innehåller noder ${\displaystyle 3=2^{1}+2^{0},5=2^{2}+2^{0},6=2^{2}+2^{1},...$ } föräldern till en given nod kan hittas genom att radera den sista inställda biten (LSB) i dess index, motsvarande den minsta potensen 2 i dess summa. Till exempel är föräldern för 6 = 110 ₂ 4 = 100 ₂ .

Diagrammet nedan visar strukturen för ett 16-nods Fenwick-träd, motsvarande en 15-elements array A:

Avbildning av ett 16-nods Fenwick-träd som innehåller intervallsummor av en 15-nodsmatris A

Låt $A(i,j]=\{A[k]\}_{k=i+1}^{j}$ . Värdet på en nod vid index $i$ motsvarar intervallsumman av element i $A(\mathrm {parent} (i) ,i]$ , det vill säga värdena på A som börjar efter förälderns index upp till den aktuella nodens index, inklusive Elementen $A(\mathrm { parent} (i),i]$ anses vara "ansvarsområdet" för den aktuella noden och består av $\mathrm {lsb} ( i)=(i\ \&\ (-i))$ (där & betecknar bitvisa OCH) element. Observera att indexen i detta intervall inte direkt motsvarar underordnade $i$ : till exempel intervallet ansvar för nod 2 är $A(0,2]=\{A[1],A[2]\}$ men nod 1 är inte ett barn till nod 2. Rotnoden 0 innehåller summan av det tomma området $A(0,0]=\{\}$ med värdet 0.

Vanligtvis implementeras Fenwick-trädet som en implicit datastruktur med användning av en platt array som är analog med implementeringar av en binär heap . I denna representation utelämnas rotnoden 0 och arrayindexen motsvarar direkt nodindex i trädet (med 1-baserad indexering).

Den första processen att bygga Fenwick-trädet över en värdetabell körs i ${\displaystyle O(n)}-$ tid. Andra effektiva operationer inkluderar att lokalisera indexet för ett värde om alla värden är positiva, eller alla index med ett givet värde om alla värden är icke-negativa. Det stöds också skalningen av alla värden med en konstant faktor i $O(n)$ tid.

Områdesfråga

För att hitta prefixsumman upp till ett givet index ( operationen "intervallfråga" ), addera värdena för noder längs vägen från det aktuella indexet till roten av trädet (vilket är trivialt en tom summa, 0). Antalet värden som ska adderas (exklusive den implicita roten) är lika med antalet 1-bitar i indexet och är som mest $\lceil \log _{2}n\rceil$ , vilket ger en tidskomplexitet av $O(\log n)$ .

Säg till exempel att man vill hitta summan av de första elva värdena. Elva är 1011 ₂ i binärt. Detta innehåller tre 1-bitar, så tre nodvärden måste läggas till: de vid noderna 11=1011 ₂ , 10=1010 ₂ och 8=1000 ₂ (den implicita rotnoden av 0000 ₂ kan ignoreras). Dessa innehåller summan av A[11], A[9,10] respektive A[1,8] (där A[i,j] = {A[i], A[i+1], .. ., A[j]}).

Punktuppdatering

För att uppdatera värdet i ett Fenwick-träd vid index $i$ (motsvarande att tilldela $A[i]$ ett nytt värde) ( operationen "punktuppdatering" ):

• Beräkna deltat ${\textstil \delta =A[i]_{\mathrm {ny} }-A[i]_{\mathrm {gammal} }}$ .
• Sedan, medan index $i\leq n$ :
  • Uppdatera indexet genom att lägga till LSB: $i\leftarrow i+(i\ \&\ (-i))$
  • Lägg till $\delta$ till värdet vid nod $i$ .

Intuitivt kan detta ses som att uppdatera varje nod (som börjar med $i$ och itererar i ökande ordning) vars ansvarsområde inkluderar $A[i]$ .

Till exempel, uppdatering av värde 11=1011 ₂ i en 16-elementarray kräver uppdatering 1011 ₂ , (1011 ₂ + 1 ₂ = 1100 ₂ ) och (1100 ₂ + 100 ₂ = 10000 ₂ ). Dessa innehåller summan av A[11], A[9,12], respektive A[1,16]. Återigen, det maximala antalet noder som behöver uppdateras begränsas av antalet bitar i arrayens storlek, $\lceil \log _{2}n\rceil$ , och tidskomplexiteten är alltså $O(\log n)$ .

Bygger trädet

Ett naivt sätt att konstruera trädet skulle vara att initiera trädvärdena till 0 och utföra $n$ punktuppdateringar, vilket ger en tidskomplexitet av $O(n\log n)$ . Men ett alternativt tillvägagångssätt använder dynamisk programmering för att bygga upp trädet stegvis längs ökande index. Initieringen fortsätter enligt följande:

• Kopiera array $A[n]$ till array $T[n]$ som innehåller trädvärden
• För varje index i från 1 till n:
  • Låt $j=i+(i\ \&\ (-i))$ . Detta är den första noden större än $i$ som innehåller $A[i]$ i sitt ansvarsområde.
  • Om $j\leq n$ , uppdatera nodens värde vid j: $T[j]\leftarrow T[j]+T[ i]$

Det kan visas att vid den punkt som index $i$ nås i loopen, är $T[i]$ redan det korrekta Fenwick-värdet för nod $i$ . Om $i$ är en lövnod (med endast ett element i sitt ansvarsområde) gäller detta trivialt. Om $i$ är en intern nod, säkerställer loopen att den har uppdaterats med alla intervallsummor inom sitt eget intervall, så den kommer att innehålla det korrekta Fenwick-värdet. Till exempel, vid steg ${\displaystyle i=4} kommer$ nod 4 (med initialvärde $A[4]$ ) att ha ökats med $T[2 ]$ (som innehåller summan $A[1]+A[2]$ ) och $T[3]$ (som innehåller värdet $A[3]$ ), och kommer således att innehålla intervallsumman $A(0,4]$ av de fyra första elementen i trädet.

Eftersom varje uppdatering sker högst en gång per index, är den resulterande algoritmen $O(n)$ tidskomplexitet. Detta kan också göras på plats i originalmatrisen, vilket eliminerar kopian och extra lagring för $T[n]$ .

En analog operation kan utföras för att omvandla ett Fenwick-träd tillbaka till den ursprungliga frekvensmatrisen ${\displaystyle A[n]} , genom att iterera$$j=i+(i\ \&\ (-i))$ från n till 1 och subtrahera värdet av från värdet av $i$ vid varje tidssteg.

En mindre effektiv ${\displaystyle O(n)}-$ algoritm för att konstruera trädet fungerar i två omgångar: konvertera först $A[n]$ till en prefixsumma (som tar $O(n)$ tid), sedan itererande bakåt från n..1, beräkna varje nods intervallsumma genom att beräkna skillnaden mellan prefixsummor: $\Sigma A(\mathrm {parent} (i),i]=\Sigma A(0,i]-\Sigma A(0,\mathrm {förälder} (i)]$ .

Förlängning till flera dimensioner

Ett 2D Fenwick-träd (2D BIT) kan konstrueras som ett 1D Fenwick-träd där varje nod i trädet innehåller ett 1D Fenwick-träd och lagrar intervallsummor för submatriser av en 2D-matris A [ m ,n]. Trädrepresentationen förblir implicit och data lagras i en m x n array där position (i, j) i arrayen motsvarar den j:te noden i det i:te Fenwick-trädet.

Punktuppdatering och intervallfråga implementeras på samma sätt som 1D-fallet, men med hjälp av kapslade loopar (itera längs kolumndimensionen (underträdet) i den inre slingan och iterera längs raddimensionen (huvudträdet) i den yttre slingan).

Denna idé kan utökas till tensorer med godtyckligt antal dimensioner d, med tidskomplexitet $O(\log ^{d}n)$ för områdesfråga och punktuppdatering (förutsatt att tensorn är är storlek n längs varje axel).

Genomförande

Grundläggande implementering i C

 






   
	   0
	    0   
		  
	 



     
	   0 
		0  
		
	
	      
		  
 // STORLEK ska vara 1 + en potens av 2.  int  A  [  STORLEK  ];  // Minst signifikanta bit av i som har värdet 1  #define LSB(i) ((i) & -(i))  // Returnerar summan av de första i-elementen (index 0 till i)  // Ekvivalent med range_sum( 0, i)  int  prefix_sum  (  int  i  )  {  int  summa  =  A  [  ];  för  (;  i  !=  ;  i  -=  LSB  (  i  ))  summa  +=  A  [  i  ];  retursumma  ;  _  }  // Lägg till delta till element med index i (nollbaserat)  void  add  (  int  i  ,  int  delta  )  {  if  (  i  ==  )  {  A  [  ]  +=  delta  ;  återvända  ;  }  för  (;  i  <  STORLEK  ;  i  +=  LSB  (  i  ))  A  [  i  ]  +=  delta  ;  } 

Användbara funktioner i C

     
	   0
	       
		  
	       
		  
	 



  
	         
		     
		   
			  
	



  
	         0  
		     
		   
			  
	



   
	    



     
	   




    
	   0     
	

      0
	    0     
		            
			    
			  
		
	
	 
 // Returnerar summan av element från i + 1 till j  // Motsvarar prefix_summa(j) - prefix_summa(i), men något snabbare  int  range_sum  (  int  i  ,  int  j  )  {  int  summa  =  ;  för  (;  j  >  i  ;  j  -=  LSB  (  j  ))  summa  +=  A  [  j  ];  för  (;  i  >  j  ;  i  -=  LSB  (  i  ))  summa  -=  A  [  i  ];  retursumma  ;  _  }  // Konvertera A[] på plats till Fenwick-trädformen  void  init  (  void  )  {  for  (  int  i  =  1  ;  i  <  SIZE  ;  ++  i  )  {  int  j  =  i  +  LSB  (  i  );  if  (  j  <  STORLEK  )  A  [  j  ]  +=  A  [  i  ];  }  }  // Konvertera tillbaka till array av per-element räknar  void  fini  (  void  )  {  for  (  int  i  =  STORLEK  -  1  ;  i  >  ;  --  i  )  {  int  j  =  i  +  LSB  (  i  );  if  (  j  <  STORLEK  )  A  [  j  ]  -=  A  [  i  ];  }  }  // Returnera ett enskilt elements värde  int  get  (  int  i  )  {  return  range_sum  (  i  ,  i  +  1  );  }  // Ange (i motsats till att justera) ett enskilt elements värde  void  set  (  int  i  ,  int  värde  )  {  add  (  i  ,  värde  -  få  (  i  ));  }  // Hitta det största i:et med prefix_sum(i) <= värde.  // OBS: Kräver att alla värden är icke-negativa!  unsigned  int  rank_query  (  int  värde  )  {  int  i  =  ,  j  =  STORLEK  -  1  ;  // j är en potens av 2.  värde  -=  A  [  ];  för  (;  j  >  ;  j  >>=  1  )  {  if  (  i  +  j  <  STORLEK  &&  A  [  i  +  j  ]  <=  värde  )  {  värde  -=  A  [  i  +  j  ];  i  +=  j  ;  }  }  returnera  i  ;  } 

Implementering i C++

  

     

        
             
    

        
             
    


        0 
    

        
           0
        
           0 
              
              
        
         
    

         
        
            
              
              
        
    
 klass  FenwickTree  {  privat  :  vektor  <  int  >  data  ;  int  getParent  (  int  i  )  const  {  return  i  -  (  i  &  (  -  i  ));  }  int  getNext  (  int  i  )  const  {  return  i  +  (  i  &  (  -  i  ));  }  public  :  FenwickTree  (  int  n  )  :  data  (  n  +  1  ,  )  {  }  int  getSum  (  int  i  )  const  {  int  summa  =  ;  ++  i  ;  while  (  i  >  )  {  summa  +=  data  [  i  ];  i  =  getParent  (  i  );  }  returnera  summan  ;  }  void  update  (  int  i  ,  int  v  )  {  ++  i  ;  while  (  i  <  data  .  size  ())  {  data  [  i  ]  +=  v  ;  i  =  getNext  (  i  );  }  }  }; 

Se även

• Beställ statistikträd
• Prefix summor
• Segment träd

externa länkar

• En handledning om Fenwick Trees på TopCoder
• En artikel om Fenwick Trees på Algorithmist
• Ett inlägg om Fenwick Trees på Polymath wiki
• stack utbyte