Segment Tree / BIT

Nasıl düşünülür

Önek toplamı aralık toplamını O(1)’de verir, ama bir değer değişirse sonrasındaki her önek O(n)’de yeniden hesaplanmalı. Fenwick tree (BIT) bunu, i indeksinin lowbit(i) uzunluğunda aralığın toplamını sakladığı zekice bir dizi ile düzeltir. Güncelleme: her ata indekse ekle. Sorgu: her ata öneki topla. İkisi de bit hileleriyle O(log n).

Segment tree tersinmez işlemlere (min, max, count) genelleşir. Dizi üzerinde bir ikili ağaçtır: her düğüm aralığının agregatını saklar. Yapraklar elemanlar; iç düğümler iki çocuğu birleştirir. Nokta güncelleme bir kök-yaprak yolunda yürür; aralık sorgusu yalnızca örtüşen düğümlere iner. Aralık güncellemeleri ([l, r] aralığındaki her elemana v ekle) için lazy propagation ekle: çocuk güncellemelerini bir sorgu dokunana kadar ertele.

Şablon şekilleri

Şekil	Temel hamle	Örnek
BIT (nokta, aralık toplam)	update(i, +v), query(r), query(l-1)	LC 307
Segment tree (aralık min/max)	Kur, nokta güncelle, sorguda birleştir	LC 315
Lazy propagation (aralık ekle)	İnişte lazy tag it, dönüşte çek	LC 1649
2D segment tree	Satır × sütun ağaçların ağacı	LC 308

Karmaşıklık temeli

Kurulum: O(n) (veya naif O(n log n)). Güncelleme: O(log n). Sorgu: O(log n). Alan: BIT O(n), segment tree O(4n) (güvenli dizi boyutu). Lazy propagation ziyaret edilen düğüm başına O(1) ekler.

Şablondan probleme

1. Karar ver: işlem tersinir mi (sum, xor) → BIT? Tersinmez mi (min, max) → segment tree?
2. BIT için dahili olarak 1-indexed kullan (update(i+1)); segment tree 0-indexed olabilir.
3. Aralık güncellemeleri için lazy propagation uygula veya BIT ile fark-dizisi hilesi kullan.
4. Sorgular statikse (güncelleme yok) sade önek toplamı daha basit ve hızlıdır.

/**
 * Segment Tree / BIT template.
 * This skeleton implements a Fenwick tree (BIT) for point-update range-sum.
 * A segment tree handles the same range queries plus non-invertible operations
 * (min, max, count); see the guide for the tree structure.
 */

export class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

/**
 * Segment Tree / BIT template.
 * This skeleton implements a Fenwick tree (BIT) for point-update range-sum.
 * A segment tree handles the same range queries plus non-invertible operations
 * (min, max, count); see the guide for the tree structure.
 */

export class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}