---
# System prepended metadata

title: CSES Josephus Problem II 範例筆記 & BIT原理統整

---

# Josephus Problem II
這題是排在CSES裡的Sorting and Searching分類裡
解法大多是使用Binary-Index-Tree(或稱Fenwick Tree)
BIT是個剛開始學/會覺得很靠北的演算法，它的原理有點通靈
這就來為各位講解一下CSES裡的Josephus Problem II

# **範例程式**

```
#include <bits/stdc++.h>
using namespace std;
 
struct Fenwick {
    vector<int> bit;
    int n;
    Fenwick(int n) : n(n), bit(n+1, 0) {}
    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    int kth(int k) { // 找第 k 個活著的人
        int idx = 0;
        int mask = 1 << (31 - __builtin_clz(n));
        for (; mask; mask >>= 1) {
            int next = idx + mask;
            if (next <= n && bit[next] < k) {
                k -= bit[next];
                idx = next;
            }
        }
        return idx + 1;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    long long k;
    cin >> n >> k;
 
    Fenwick fw(n);
    for (int i = 1; i <= n; i++) fw.add(i, 1);
 
    int pos = 1; // 從第 1 個小孩開始
    for (int rem = n; rem > 0; rem--) {
        long long step = k % rem + 1; //要走幾步才會到指定位置
        int curr_sum = fw.sum(pos - 1); //需要[1, pos-1]的總和
        int target_sum = (curr_sum + step) % rem;
        if (target_sum == 0) target_sum = rem;
        int idx = fw.kth(target_sum);
        cout << idx << (rem == 1 ? '\n' : ' ');
        fw.add(idx, -1);
        pos = idx;
    }
}

```
## 將n固定為8的範例   
//* ------------------ 最小示範 ------------------
   1) 建立 n=8 的 Fenwick
   2) 將 a[i] 全部設為 1（代表 8 個活著）
   3) 查 sumPrefix(7) 與區間和
   4) 刪掉位置 3（add(3,-1)）
   5) 用 kth(第5個1) 反查座位
*//
```
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 8;
    Fenwick fw(n);

    // 將 a[1..n] 全設為 1
    for (int i = 1; i <= n; ++i) fw.add(i, 1);

    cout << "sumPrefix(7) = " << fw.sumPrefix(7) << "\n";      // 7
    cout << "sumRange(3,6) = " << fw.sumRange(3, 6) << "\n";   // 4

    // 刪掉位置 3（活著→死亡）
    fw.add(3, -1);
    cout << "after remove 3, sumPrefix(7) = " << fw.sumPrefix(7) << "\n"; // 6

    // 找目前第 5 個活人是誰（原本 {1..8}，去掉 3，活人是 {1,2,4,5,6,7,8}，第5個=6）
    int pos = fw.kth(5);
    cout << "kth(5) = " << pos << "\n"; // 6

    return 0;
}
```

Fenwick Tree 的「選擇性查詢」：
從最高位 bit 開始二分
⬇
累積和小於 k 的話，向右移動
⬇
最後得到的位置就是**第 k 個活著的人的編號**

每次跳 k 個人
要找第pos個小孩
把所有含pos的bit段落更新
(以上是主要操作原理，如果看不懂，建議先看後面的設定和原理)


# **設定**
我們用 alive[i] 表示 i 是否還活（活=1、死=0）。

> add(i, delta)：更新位置 i 的值，加上 delta（O(log n)）
> 
> 
> 刪掉一個人就是 add(pos, -1)


> sum(i)：求 1 到 i 的前綴和（O(log n)）
> 
> 
> 代表目前有多少人位置 ≤ i


> sumPrefix(x) = 1..x 的活人數。


> rem = 目前剩下的人數。


我們把「跳 k 個，刪下一個」轉成「以活人次序（rank）來找人」：


> 每輪的有效步數：step = (k % rem) **+ 1** (加我現在站的區塊)


> 當前「起點」的活人次序：curr = sumPrefix(pos-1)


> 目標活人次序：target = (curr + step) % rem；若為 0，用 rem


用 BIT 反查「第 target 個活人」得到實際座位 idx，刪掉他


下一輪的起點 pos = idx 的下一個還活著的人（環狀，若沒有就繞回最小活人）


**核心：我們一直在找「第 target 個活著的人」。**
 sumPrefix() 用來把位置 ↔ 活人次序在 O(log n) 內互相對照（**反查用 kth**）。

# **查詢&更新原理**
### 問題1
 **1) idx 是什麼？放進 BIT 的原理是什麼？初始值是什麼？**
idx 就是 bit 的索引，同時也對應到原陣列 (alive[1...i]) 的某個尾端位置。
Fenwick Tree 用一個同樣長度的陣列 bit[1..n] 來「壓縮存取」
bit[idx] 不是只存 a[idx]，而是存 一段（下面第 2 點說明）。
### 問題2
**2) 「長度為 lowbit(idx) 的區段總和」是怎麼切？過程與最後值是什麼？**

lowbit(idx) 是二進位中 idx **末尾連續 0 的「對應 2^r」那一位。**

***這格管的區間長度=lowbit[這格的值]***

|分類代表⬇數字(n)➡| 1 | 2 | 3 |4 | 5 | 6 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
|二進制(末位有幾個連續的0)| 001   | 01**0**    | 011     | 1**00**    | 101    | 11**0**    |
|bit[n]管理範圍| [1,1]| [1,2]| [3,3]| [1,4] | [5,5] | [5,6]|
|管理幾個數字"lowbit[n]"| 2^0 = 1| 2^1 = 2| 2^0 = 1| 2^2 = 4 | 2^0 = 1 | 2^1 = 2|

**上述lowbit():**
2^0 = 1(lowbit) “因為末尾是1，沒有0”
2^1 = 2 **“因為末尾是0，有幾個0，2就有幾次方”**
 依此類推 | 以下

### 問題3
**3) 為何 bit[idx] 覆蓋的範圍是[idx - lowbit(idx) + 1, idx]？**
Fenwick Tree 的結構設計就是「每個 idx 管理一段以 idx 為結尾、長度 = lowbit(idx) 的區間」

這樣定義能保證：
所有前綴和 sumPrefix(i) 都能被幾個「不重疊」的 bit[...] 區間拼起來（下一點會用到）。

### 問題4
**4) 為何「沿著涵蓋 i 的那些區段往上/下跳」就能解決更新與查詢？**
那就需要分成「更新」與「查詢」兩件事來說：

> 函式: add(原陣列裡的第i個數, 原值+delta)
---------
#### 查詢
查詢是把 1..i 切成不重疊的段，一段一段讀值加起來
> i -= lowbit(i)

例: bit[4]&bit[6] 可拼成1~6的段落
把所有查出的bit[x]的值加總
就可以得到所要段落總和

-----
#### 更新
pos[n]更新是找所有含 n 這個值的段，把它們的值更新掉
> i += lowbit(i)

n = 8 , pos = 7 , 更新bit[7]、bit[8] (若n=8,僅這兩個bit有儲存"7"這個數字)
bit[7] = [7,7] (含7)
bit[8] = [1,8] (含7)

--------
#### 原理總結(很重要)
**它們走的方向相反：**
**查詢：i -= lowbit(i)（往回跳）**
**更新：i += lowbit(i)（往前跳）**


