# BIT - Cây phân đoạn

### Kiến thức cần nắm:
**[Bitwise Bù trừ 2](https://hackmd.io/@c3jv2tKJQeqHkvfbGE2CSA/B1uORSiKgx)**

**Một số tính chất Bitwise cần nhớ**:

- $-i \,\&\, i = (\sim i + 1) \,\&\, i = \text{lsb}(i)$

**vì**:
- $\sim i \,\&\, i = 0$
- $\sim i + 1$ sẽ cộng vào bit thứ $0$ của $i$, khi đó:
- Nếu tại đó là $0$ thì biến $0$ thành $1$.
- Nếu tại đó là $1$ thì nó sẽ biến bit $0$ gần nhất thành $1$ (vì nếu tại $\sim i$ là $0$ thì tại $i$ nó là bit $1$).
- Còn những bit $1$ liên tiếp đó khi cộng $1$ vào sẽ bị biến thành $0$ để khi AND thì ra $0$ (còn đoạn bit $1$ prefix thì vẫn giữ nguyên vị trí và **AND** cũng ra $0$).

**Một vài định nghĩa:** $lsb(x)$ là $-x\&x$, là bit $1$ **phải nhất** của $x$ $($cũng là số có dạng $2^{k}$ **lớn nhất** sao cho $2^{k}$ $|$ $i$ , **c\m** bằng cách đặt nhân tử chung$).$

---

### Nhận xét chính:
- Mỗi $idx$ khi tăng lên sẽ sinh ra bit $1$ tại vị trí khác nhau.
- Nhưng nó sẽ còn trùng **prefix** với $idx - 1$, còn bit mới sẽ được tính riêng (và nó sẽ chứa $-x \,\&\, x = 2^{\text{bit bé nhất của } idx}$ phần tử mới nhất vì những đoạn trước đã được chứa rồi).
- Đoạn **prefix** sẽ được binary-lift qua (vì đã tính trước đó).
- Khi đạt tới dạng $2^k$ thì nó reset lại từ đầu.

$\Rightarrow$ Mỗi vị trí $idx$ sẽ quản lí những phần tử $a[i]$ nhất định, khi update chỉ cần tìm những đoạn đó để **update** là xong.

---

### Thao tác Get:

**Ví dụ**:

- $idx = \texttt{01110001011100[1000]}$

thì nó sẽ quản lí đoạn **suffix** dài $1000$ $($tức dài $2^{3}$, ghi $1000$ cho dễ hình dung$)$ và lấy thêm **kq** của đoạn:

- $\texttt{01110001011100[0000]}$.

Sau đó nó sẽ nhảy sang đoạn có độ dài

- $\texttt{01110001011[1000000]}$.

Tiếp đó, nó sẽ quản lí suffix dài $1000000$ và nó sẽ lấy thêm **kq** của đoạn dài :

- $\texttt{0111000101[10000000]}$.

Cứ lặp như vậy cho tới khi nào tới đoạn:

- $\texttt{0[10000000000000000]}$

thì ta thấy rằng đoạn trên sẽ quản lí full đoạn của nó $($tức $[1 \dots 0\texttt{10000000000000000}]$, vì **idx** có dạng $2^{x}$ sẽ quản lí **full** đoạn$)$.

Cộng lại những đoạn trên ta ra được tổng từ $[1 \dots idx]$.

$\Rightarrow$ Độ phức tạp là **số bit bật** (rất dễ 😎).

---
### Thao tác Update

Từ quan sát ở thao tác **get**, ta thấy được số **phần tử** của cây **BIT** là:
- Đối với $1$ loại $lsb(x)$ thì số lượng số có $lsb$ đó là $2^{log(n) - lsb(x)}$ $^{position}$
- Có $log_{2}(n)$ loại $lsb$ **khác nhau**.

$\Rightarrow$ **Vậy**:

**Từ nhận xét trên ta có biểu thức**:

-Gọi $\ell$ là $log_{2}(n)$:

$E = 2^{\ell} \cdot 2^0 + 2^{\ell-1} \cdot 2^1 + 2^{\ell-2} \cdot 2^2 + \dots + 2^0 \cdot 2^{\ell}$

**Mỗi số hạng đều bằng**:

$2^{\ell-k} \cdot 2^k = 2^{\ell}$

Có tổng cộng $\ell+1$ số hạng.

**Do đó**:

$E = (\ell+1) \cdot 2^{\ell}$

Vì $2^{\ell} = n$ và $\ell = \log_2 n$, ta được:

$E = (\log_2 n + 1) \cdot n$

Vậy, **số phần tử** $($tức là **đpt** khi nó **update** $n$ phần tử$)$ của cây BIT là:

$E \approx n \log(n)$

---

### Vậy làm sao để tìm những bit mà chứa $a[i]$?

**Quan sát**:
- Đoạn mà $bit[j]$ sẽ quản lí là $[j - \text{lsb}(j) + 1, \, j]$.
- Vậy thì một $bit[j]$ mà để chứa được $a[i]$ thì phải thỏa:

$$ j - \text{lsb}(j) + 1 \leq i \leq j $$

$\Rightarrow i \in [j - \text{lsb}(j) + 1, \, j]$.

---

### Ví dụ:

Xét $idx = \texttt{011100010111001000}$

- Điều hiển nhiên là **idx** bé nhất chứa $a[i]$ chính là $i$ rồi.
- Dự đoán hình dạng của **idx** chứa $a[i]$:

Có dạng:
- $j \geq i$
- Bỏ $\text{lsb}(j)$ đi thì $j \leq i$

Quan sát lại $idx$ trong ví dụ trên thì:

- Khi cho $1$ bit vào $idx$ đó thì chắc chắn $j > idx$.
- Đằng trước nó phải không được phép có bit $1$ nào, vì: nếu có thì bit $1$ đó sẽ là $\text{lsb}$ của $j$, mà khi bỏ ra thì $j < idx$.
- Do đó bit $1$ vừa thêm vào sẽ là $\text{lsb}(j)$.
- Khi tạo $j$ mới thì nó **không được phép** đặt nhiều hơn $1$ bit vào vị trí bit $0$.

---

### Phân loại $j$:

Có bao nhiêu loại $idx \, j$ mà $j > idx$?

**1.** Có $> 1$ bit nằm ở vị trí cao hơn bit $1$ cao nhất của $idx$.
**2.** Có đúng $1$ bit nằm cao hơn bit $1$ cao nhất của $idx$.
**3.** Có cùng prefix với $idx$ và có $1$ bit đặt tại vị trí mà ở đó $idx$ là $0$, và suffix có một vài bit $1$.
**4.** Giống loại $(3)$ nhưng không có suffix.
**5.** Có duy nhất $1$ bit nằm cao hơn bit cao nhất của $idx$, còn prefix và suffix full $0$.
**6.** Có trùng prefix với $idx$, có $1$ bit trùng với vị trí bit $1$ của $idx$ nhưng không có suffix.

---

### Kết luận:
- TH **(1)**, **(2)**, **(3)** $\;\Rightarrow\;$ không hợp lệ $($vì $j - \text{lsb}(j) > i$$)$.
- TH **(6)** $\;\Rightarrow\;$ bản thân nó đã $< i$.
- Hợp lệ: TH **(4)**, **(5)**.

$\Rightarrow$ Có thể hình dung được hình dạng của $idx \, j$ mà chứa được $a[i]$.

---

### Vòng for trong update:

for(; idx <= n; idx += -idx & idx)

**Độ phức tạp:** Với mỗi `a[i]` thì TH tệ nhất là mỗi lần nó cộng cho $2^{k}$ $+$ $2^{k+1}$ $+...+ 2^{log_{2}(n)}$ nên với $n$ phần tử thì tốn **nlogn**

---

### Các phiên bản khác

**Phiên bản ko Latex (100% của mình edit, bản trong HackMD được format lại bởi GPT):** **[Click vào đây](https://surl.lu/heydql)**

**Phiên bản GPT chỉnh sửa lại (GPT tự chấm 95/100):** **[Click vào đây](https://surl.li/ccgcqj)**

**Đánh giá của GPT về blog này:** **[Click vào đây](https://surl.li/zwxcpw)**