# 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)（往前跳）**
Sign in with Wallet
Connect another wallet