What and When to Use Advanced DS (Fenwick Tree, Segment Tree - conceptual)

What and When to Use Advanced DS (Fenwick, Segment Trees)

Use these for fast range queries and updates when arrays are too slow.

---

Fenwick Tree (Binary Indexed Tree)

Supports prefix sums and point updates in O(log N) with tiny constants.

class Fenwick {
  constructor(n){ this.n=n; this.bit=Array(n+1).fill(0) }
  add(i,delta){ for(i++; i<=this.n; i+=i&-i) this.bit[i]+=delta }
  sum(i){ let s=0; for(i++; i>0; i-=i&-i) s+=this.bit[i]; return s }
  range(l,r){ return this.sum(r)-this.sum(l-1) }
}

---

Segment Tree

Generalizes to many associative operations (min, max, sum) and supports range updates with lazy propagation.

class SegTree {
  constructor(a){ this.n=1; while(this.n<a.length) this.n<<=1; this.t=Array(2*this.n).fill(0); for(let i=0;i<a.length;i++) this.t[this.n+i]=a[i]; for(let i=this.n-1;i>=1;i--) this.t[i]=this.t[2*i]+this.t[2*i+1] }
  query(l,r){ l+=this.n; r+=this.n; let res=0; while(l<=r){ if(l&1) res+=this.t[l++]; if(!(r&1)) res+=this.t[r--]; l>>=1; r>>=1 } return res }
  update(i,val){ i+=this.n; this.t[i]=val; for(i>>=1;i>=1;i>>=1) this.t[i]=this.t[2*i]+this.t[2*i+1] }
}

Pick based on operation complexity, update/query frequency, and memory.