Bugün fenwick ağaçları (ikili indeksli ağaçlar) hakkında bir konferans dinledim ve öğretmen bu ağacın aralık ve segment ağaçlarının bir genellemesi olduğunu söylüyor, ancak bu üç veri yapısına ilişkin uygulamalarımız farklı. Bu doğrudur mu? ve neden?Aralık, segment, fenwick ağaçları aynı mıdır?
Hiç bir şeyin genelleştirilmesi olarak adlandırılan binary indexed trees duymadım. Bu kesinlikle interval trees ve segment trees'un bir genelleştirmesi değildir. Kendinizi buna ikna etmek için bağlantıları takip etmenizi öneririm. Bu ağacın daha
o yanlıştır, aralık ve segment ağaçları
"bu ağacın" ederek öğretmen "ikili endeksli ağaç" demekse
bir genellemedir.ama bu üç veri yapılarının benim uygulamaları
Öğretmeniniz onlar olmamalı demedim, onlar farklıdır Tabii
farklıdır. Sadece birinin diğerinin genelleştirilmesi olduğunu söyledi (ki bu doğru değil, ama hala). Her iki durumda da, uygulamaların farklı olması gerekiyordu. olanlar aynı şeyçünkü aynı uygulama olurdu ne
, bir ikili endeksli ağacı ve bir fenwick ağacıdır.
Topcoder'ın makalesini gördüm ve BIT'deki birçok sorgu aralıklı ağaçlara benziyor. – Luiguis
Benzer olabilir, ancak bu, bir veri yapısının bir diğerinden kaynaklandığını söyleyebileceğiniz anlamına gelmez. Aralık ağacındaki bir düğüm, ana düğümün tuttuğu aralığın yarısını tutarken, BIT'deki bir düğüm, bir sayının ikili temsili tarafından verilen bir aralığa sahiptir. – IVlad
Aşağıdaki sınıflandırma mantıklı görünüyor, ancak farklı insanlar bu terimleri karıştırmak zorunda kalıyor.
Fenwick ağaç/Binary-endeksli ağaçlink
Eğer önek meblağlar (diğer adıyla kümülatif toplamlar) depolamak için ikili gösterimine tek bir dizi ve operasyonları kullandığınız bir. Elementler bir monoid üyesi olabilir.
sınıf ağaçlink
her bir düğüm belirli bir aralıkta bir subrange temsil ağaç ailesi, ki [0, N],. Aralıklardaki ilişkisel işlemleri hesaplamak için kullanılır. Eğer gerçek aralıklarını depolamak
Aralığı ağaçlink
Ağaçlar. En sık olarak bir orta noktayı alırsınız, kesişen aralıkların düğümde kalmasını sağlayın ve aralıklar için noktaların sola ve sağına kadar tekrarlayın. Yaprakları bir olasılıkla sürekli uzayda ilköğretim aralıkları yerine ayrık ve yüksek düğümleri olduğu bir dizi ağacına benzer
Segment ağaçlink
ilköğretim aralıkları birlikleri bulunmaktadır. Nokta eklenmesini kontrol etmek için kullanılır.
"A, B'nin genelleştirmesi" ve "A'nın B ile aynı olduğunu" belirten bir fark vardır. –