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.
التالي · الدرس 87 من 92
Common Problem Solving Patterns (Sliding Window, Two Pointers, etc.)
قراءة 1 دقيقة
أنهيت 86 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

