Problem link ও উৎস
- **Original source:** CSES Problem Set — "Salary Queries"
- **Platform:** CSES —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Hard
- **Pattern:** BIT over compressed values (value-দের উপর frequency table)
- **Basic idea inherited from:** coordinate compression, BIT
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা company-তে `n`-জন কর্মী, প্রত্যেকের একটা করে salary আছে। তারপর `q`-টা ঘটনা একে একে আসে, দুই ধরনের —
- `! k x` — কর্মী `k`-র salary বদলে `x` করো।
- `? a b` — এই মুহূর্তে কতজন কর্মীর salary `[a, b]` range-এ আছে (দুই প্রান্ত সহ)?
প্রতিটা `?` query-র উত্তর দাও।
```text
salaries: [2200, 1500, 3000] (কর্মী 1, 2, 3)
? 2000 3500 -> 2 (2200 আর 3000)
! 1 4500 (কর্মী 1-র salary এখন 4500)
? 2000 3500 -> 1 (শুধু 3000, 2200 এখন 4500 হয়ে range-এর বাইরে)
? 4000 5000 -> 1 (4500)
```
### Input ও output {#8-example-input-and-output}
```text
salaries = [2200, 1500, 3000]
? 2000 3500 -> 2
! 1 4500 (কর্মী 1: 2200 -> 4500)
? 2000 3500 -> 1
? 4000 5000 -> 1
? 1000 5000 -> 3
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বিশাল হলঘরে salary-অনুযায়ী সাজানো খোপ — সবচেয়ে কম থেকে সবচেয়ে বেশি। প্রতিটা কর্মী তার salary-র খোপে একটা করে টোকেন রাখে।
"কতজনের salary `[a, b]`-তে" জানতে তুমি প্রতিটা খোপ গুনতে যাও না — দুটো ছোট হিসেব করো: "b পর্যন্ত মোট কত টোকেন" বিয়োগ "a-র ঠিক আগে পর্যন্ত মোট কত টোকেন"। কারো salary বদলালে শুধু একটা টোকেন পুরনো খোপ থেকে তুলে নতুন খোপে রাখো — পুরো হলঘর আবার গুনতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **coordinate compression** আর **BIT (Fenwick tree)**-এর উপর।
- **BIT** থেকে: একটা Fenwick tree-কে *value-দের উপর frequency table* হিসেবে দেখা — `add(v, +1)` মানে "একটা salary v দেখলাম", `prefix_count(v)` মানে "কতগুলো salary `<= v`" ([../fenwick-tree.md](../fenwick-tree.md) section 9-এর core idea)।
- **Coordinate compression** থেকে: salary 10^9 পর্যন্ত হতে পারে — অত বড় array বানানো অসম্ভব। তাই শুধু যে value-গুলো আসলে দেখা যায় (initial salaries + সব update-এর `x`) সেগুলোকে সংগ্রহ করে sort করে rank দাও।
দুটো মিললে: range count + update দুটোই O(log n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই ধাপের: প্রথমে **"কতগুলো ≤ v" → range count**, কারণ `count[a, b] = prefix_count(b) - prefix_count(a - 1)`। এই subtraction চলে কারণ count invertible ([../fenwick-tree.md](../fenwick-tree.md) section 6)।
দ্বিতীয়ত **value-কে position-এ বদলানো**: BIT-এর index মানে এখানে একটা *value-র rank*, কর্মীর position নয়। তাই 10^9-এর range-কে compress করে ছোট index-space-এ আনা হয়, যাতে BIT array ছোট থাকে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **Fenwick tree (BIT)**, যেখানে index = compressed salary rank, আর `tree[r]` ওই rank-এ কতজন আছে তার count জমায়। সঙ্গে দরকার:
- compressed value-দের একটা sorted list (rank ↔ value mapping),
- প্রতিটা কর্মীর বর্তমান salary রাখার একটা পাশের array (update-এ আগের value সরাতে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Update আছে, তাই plain prefix sums বাদ (একটা update পুরো prefix array ভাঙে — [../segment-tree.md](../segment-tree.md) section 1)। আর এটা count-of-values query, range-min নয় — তাই Fenwick-ই যথেষ্ট, পুরো segment tree লাগে না ([../fenwick-tree.md](../fenwick-tree.md) section 8-এর rule of thumb: point update + count = Fenwick)।
Salary বিশাল হলেও আলাদা distinct value-র সংখ্যা সীমিত (`n + q`-এর মতো), তাই coordinate compression BIT-টাকে ছোট আর দ্রুত রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: salary-গুলো একটা list-এ রাখো। প্রতিটা `?` query-তে পুরো list ঘেঁটে `a <= s <= b` গোনো; প্রতিটা `!` update-এ ওই কর্মীর salary সরাসরি বদলে দাও।
```text
? a b: count = sum(1 for s in salary if a <= s <= b)
! k x: salary[k] = x
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা `?` query পুরো `n`-জন কর্মী scan করে — O(n)। `q`-টা query থাকলে মোট **O(n·q)**, আর `n, q` দুটোই 2·10^5 হলে প্রায় 4·10^10 — time limit exceeded। count আর update দুটোকেই O(log n)-এ নামাতে BIT লাগবে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **range count = দুটো prefix count-এর বিয়োগ**, আর prefix count মানে "≤ v কতজন" — যেটা Fenwick frequency tree ঠিক যা দেয়। তাই salary-কে rank-এ বদলে BIT-এ count জমালে, প্রতিটা query/update O(log n)। index এখানে value-র rank, কর্মীর নয় — এই shift-ই পুরো trick।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব value (initial + future updates) আগে থেকে সংগ্রহ করো, sort করে rank দাও (offline compression)। প্রতিটা initial salary-র rank-এ `add(+1)`। তারপর events চালাও:
- `? a b` → `prefix_count(rank_of_value_le(b)) - prefix_count(rank_of_value_le(a-1))`।
- `! k x` → পুরনো salary-র rank-এ `add(-1)`, নতুন `x`-এর rank-এ `add(+1)`, পাশের array আপডেট।
দুটো প্রান্তের rank খুঁজতে compressed list-এ binary search।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "salary-গুলো position অনুযায়ী রাখব" ভাবার বদলে ভাবো "salary-গুলো *value অনুযায়ী* গুনে রাখব — BIT-এর index মানে একটা value-র rank, কর্মী নয়।" তাহলে range count স্রেফ দুটো prefix-এর বিয়োগ, আর update স্রেফ এক টোকেন এ-খোপ থেকে ও-খোপে সরানো।
### ছবিতে বোঝা {#7-visual-explanation}
salaries `[2200, 1500, 3000]`, update-এ আসবে `4500`। distinct value sort করে rank:
```text
distinct sorted values: 1500 2200 3000 4500
rank (1-indexed) : 1 2 3 4
শুরুর frequency BIT (rank-এ count):
rank: 1 2 3 4
cnt : 1 1 1 0 (1500,2200,3000 প্রত্যেকে একবার)
prefix_count(rank) = ওই rank পর্যন্ত মোট কর্মী
prefix_count(3) = 1+1+1 = 3 ("salary <= 3000": 3 জন)
prefix_count(1) = 1 ("salary <= 1500": 1 জন)
? 2000 3500: a=2000 -> rank ঠিক a-র নিচে = 1 (শুধু 1500)
b=3500 -> rank <= b = 3
count = prefix_count(3) - prefix_count(1) = 3 - 1 = 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
salaries `[2200, 1500, 3000]`, query `? 2000 3500`:
1. compressed values `[1500, 2200, 3000, 4500]`, rank 1..4। BIT count = `[1,1,1,0]`।
2. `b = 3500`: `<= 3500` সবচেয়ে বড় value 3000 → rank 3। `prefix_count(3) = 3`।
3. `a = 2000`: `a - 1 = 1999`, `<= 1999` সবচেয়ে বড় value 1500 → rank 1। `prefix_count(1) = 1`।
4. উত্তর = `3 - 1 = 2`। ✓ (2200 আর 3000)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import bisect
class Fenwick:
"""value-দের উপর FREQUENCY table। index = compressed salary rank (1-indexed)।
add(r, delta): rank r-এ count বদলাও; prefix_count(r): rank <= r মোট কতজন।
`../fenwick-tree.md` section 9-এর 'BIT as a frequency table' এখানেই কাজে লাগে।"""
def __init__(self, size):
self.n = size
self.tree = [0] * (size + 1) # 1-indexed
def add(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # পরের block-এ লাফ
def prefix_count(self, i): # rank 1..i মোট count
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # last set bit ঝাড়ো
return s
def solve(salaries, events):
"""events: ('set', k, x) বা ('query', a, b)। 'query'-গুলোর উত্তরের list ফেরে।
Offline coordinate compression: সব value আগে জড়ো করে rank দিই।"""
# 1) সব আসন্ন value সংগ্রহ (initial + future set values)
vals = set(salaries)
for ev in events:
if ev[0] == 'set':
vals.add(ev[2])
comp = sorted(vals) # rank = bisect position + 1
def rank_le(v):
# value <= v এমন সবচেয়ে বড় rank (1-indexed); কেউ না হলে 0
return bisect.bisect_right(comp, v)
bit = Fenwick(len(comp))
cur = list(salaries) # প্রতিটা কর্মীর বর্তমান salary
for s in cur:
bit.add(rank_le(s), +1) # rank_le(s) == s-এর নিজের rank
out = []
for ev in events:
if ev[0] == 'set':
_, k, x = ev
bit.add(rank_le(cur[k]), -1) # পুরনো salary সরাও
cur[k] = x
bit.add(rank_le(x), +1) # নতুন salary বসাও
else: # 'query'
_, a, b = ev
out.append(bit.prefix_count(rank_le(b)) -
bit.prefix_count(rank_le(a - 1)))
return out
def brute(salaries, events):
# obviously-correct reference: প্রতি query-তে linear scan
cur = list(salaries)
out = []
for ev in events:
if ev[0] == 'set':
cur[ev[1]] = ev[2]
else:
_, a, b = ev
out.append(sum(1 for s in cur if a <= s <= b))
return out
# ---- tests ----
salaries = [2200, 1500, 3000] # কর্মী index 0, 1, 2
events = [
('query', 2000, 3500), # -> 2 (2200, 3000)
('set', 0, 4500), # কর্মী 0: 2200 -> 4500
('query', 2000, 3500), # -> 1 (শুধু 3000)
('query', 4000, 5000), # -> 1 (4500)
('query', 1000, 5000), # -> 3 (4500, 1500, 3000)
]
assert solve(salaries, events) == [2, 1, 1, 3]
assert solve(salaries, events) == brute(salaries, events)
# range-এর বাইরে / প্রান্ত মেলানো
assert solve([5, 5, 5], [('query', 5, 5)]) == [3] # সবাই ঠিক প্রান্তে
assert solve([1, 10], [('query', 2, 9)]) == [0] # কেউ ভেতরে নেই
assert solve([1, 10], [('query', 1, 10)]) == [2] # দুই প্রান্ত inclusive
# random fuzz: compressed BIT vs brute
import random
random.seed(16)
for _ in range(300):
n = random.randint(1, 10)
sal = [random.randint(1, 50) for _ in range(n)]
evs = []
for _ in range(random.randint(1, 15)):
if random.random() < 0.4:
evs.append(('set', random.randrange(n), random.randint(1, 50)))
else:
a = random.randint(1, 50)
b = random.randint(a, 50)
evs.append(('query', a, b))
assert solve(sal, evs) == brute(sal, evs)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `Fenwick.add / prefix_count` — standard BIT: `add` lowbit যোগ করে n-এর দিকে হাঁটে, `prefix_count` lowbit বিয়োগ করে 0-র দিকে।
- `vals` / `comp` — সব initial আর future value জড়ো করে sort: offline coordinate compression, rank ঠিক হয় এখানে।
- `rank_le(v)` — `bisect_right` দিয়ে "≤ v কতগুলো compressed value" = `v`-এর (বা তার নিচের) rank।
- `solve` — initial salaries BIT-এ ভরে, প্রতিটা `set`-এ পুরনো rank `-1` নতুন rank `+1`, প্রতিটা `query`-তে দুটো prefix-এর বিয়োগ।
- `brute` — প্রতি query-তে linear count reference, BIT-এর উত্তর যাচাই করতে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[2200, 1500, 3000]`-এ প্রথম query `[2000,3500]` দেয় 2 (2200, 3000)। কর্মী 0-এর salary 2200 থেকে 4500 হলে BIT-এ 2200-র টোকেন সরে 4500-এ যায়; তখন `[2000,3500]` দেয় 1 (শুধু 3000, কারণ 2200 এখন range-এর বাইরে), `[4000,5000]` দেয় 1 (4500), `[1000,5000]` দেয় 3 (সবাই)। ফল `[2,1,1,3]`, brute-এর সাথে মেলে। প্রান্ত-মেলানো আর 300 random fuzz case-ও pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
Compression: distinct value sort, **O((n+q) log(n+q))**। প্রতিটা event-এ কয়েকটা `add`/`prefix_count` + একটা binary search — প্রতিটা **O(log(n+q))**। মোট **O((n+q) log(n+q))**।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n + q)** — BIT array distinct-value-সংখ্যার সমান, compressed value list, আর প্রতি কর্মীর বর্তমান salary।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `prefix_count(a)` ব্যবহার করা যেখানে `prefix_count(a - 1)` দরকার — তাহলে salary ঠিক `a`-তে থাকা কর্মীরা বাদ পড়ে ([../fenwick-tree.md](../fenwick-tree.md) section 6-এর off-by-one)।
- Future update-এর value-গুলো compression-এ অন্তর্ভুক্ত না করা — পরে rank খুঁজতে গিয়ে সেই value list-এ নেই।
- Update-এ পুরনো salary `-1` করতে ভুলে যাওয়া — তাহলে একই কর্মী দুবার গোনা হয়।
- BIT-এর index-কে কর্মীর position ভাবা — এখানে index মানে value-র rank।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: BIT-as-frequency-table ([../fenwick-tree.md](../fenwick-tree.md) section 9) + coordinate compression (10^9 value-কে rank-এ নামানো, এই tracker-এর #13/#14-এও একই reflex)। base BIT-এর runnable code [../implementation.py](../implementation.py)-তে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Count of Smaller Numbers After Self (BIT + compression) —