🎯 Mục tiêu

• Biết cách tính nhanh tổng đoạn, cực trị bằng cây phân đoạn.
• Hiểu cơ chế lưu mảng ở dạng cây để truy vấn O(log n).

💻 Segment Tree (C++)

struct Seg{
  int n;vector<long long> st;
  Seg(int n):n(n){st.assign(4*n,0);}
  void update(int id,int l,int r,int p,long long v){
    if(l==r){st[id]=v;return;}
    int m=(l+r)/2;
    if(p<=m)update(id*2,l,m,p,v);
    else update(id*2+1,m+1,r,p,v);
    st[id]=st[id*2]+st[id*2+1];
  }
  long long query(int id,int l,int r,int u,int v){
    if(v<l||r<u)return 0;
    if(u<=l&&r<=v)return st[id];
    int m=(l+r)/2;
    return query(id*2,l,m,u,v)+query(id*2+1,m+1,r,u,v);
  }
};

💻 Fenwick Tree (Python)

class Fenwick:
  def __init__(self,n):
    self.n=n;self.bit=[0]*(n+1)
  def update(self,i,v):
    while i<=self.n:
      self.bit[i]+=v
      i+=i&-i
  def sum(self,i):
    s=0
    while i>0:
      s+=self.bit[i]
      i-=i&-i
    return s
fw=Fenwick(5)
for i in range(1,6): fw.update(i,i)
print(fw.sum(5)-fw.sum(2))

🧩 Bài tập

1. Viết hàm query(l, r) và update(i, x) cho Fenwick Tree.
2. Tính tổng các phần tử từ 1 đến n nhanh chóng.

fw=Fenwick(10)
fw.update(3,5)
print(fw.sum(5)-fw.sum(2))