Skip to content

016 — Salary Queries

Source

  • Original source: CSES Problem Set — "Salary Queries"
  • Platform: CSES — https://cses.fi/problemset/
  • Topic: segment tree and fenwick tree
  • Difficulty: Hard
  • Pattern: BIT over compressed values (value-দের উপর frequency table)
  • Basic idea inherited from: coordinate compression, BIT

1. Problem in simple words

একটা company-তে n-জন কর্মী, প্রত্যেকের একটা করে salary আছে। তারপর q-টা ঘটনা একে একে আসে, দুই ধরনের —

  • ! k x — কর্মী k-র salary বদলে x করো।
  • ? a b — এই মুহূর্তে কতজন কর্মীর salary [a, b] range-এ আছে (দুই প্রান্ত সহ)?

প্রতিটা ? query-র উত্তর দাও।

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)

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 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 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 section 1)। আর এটা count-of-values query, range-min নয় — তাই Fenwick-ই যথেষ্ট, পুরো segment tree লাগে না (../fenwick-tree.md section 8-এর rule of thumb: point update + count = Fenwick)।

Salary বিশাল হলেও আলাদা distinct value-র সংখ্যা সীমিত (n + q-এর মতো), তাই coordinate compression BIT-টাকে ছোট আর দ্রুত রাখে।

6. Real-life analogy

ভাবো একটা বিশাল হলঘরে salary-অনুযায়ী সাজানো খোপ — সবচেয়ে কম থেকে সবচেয়ে বেশি। প্রতিটা কর্মী তার salary-র খোপে একটা করে টোকেন রাখে।

"কতজনের salary [a, b]-তে" জানতে তুমি প্রতিটা খোপ গুনতে যাও না — দুটো ছোট হিসেব করো: "b পর্যন্ত মোট কত টোকেন" বিয়োগ "a-র ঠিক আগে পর্যন্ত মোট কত টোকেন"। কারো salary বদলালে শুধু একটা টোকেন পুরনো খোপ থেকে তুলে নতুন খোপে রাখো — পুরো হলঘর আবার গুনতে হয় না।

7. Visual explanation

salaries [2200, 1500, 3000], update-এ আসবে 4500। distinct value sort করে rank:

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

8. Example input and output

salaries = [2200, 1500, 3000]

? 2000 3500 -> 2
! 1 4500          (কর্মী 1: 2200 -> 4500)
? 2000 3500 -> 1
? 4000 5000 -> 1
? 1000 5000 -> 3

9. Brute force thinking

প্রথম সরল চিন্তা: salary-গুলো একটা list-এ রাখো। প্রতিটা ? query-তে পুরো list ঘেঁটে a <= s <= b গোনো; প্রতিটা ! update-এ ওই কর্মীর salary সরাসরি বদলে দাও।

? 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 স্রেফ এক টোকেন এ-খোপ থেকে ও-খোপে সরানো।

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)

15. Python solution

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-এর উত্তর যাচাই করতে।

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!।

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 section 6-এর off-by-one)।
  • Future update-এর value-গুলো compression-এ অন্তর্ভুক্ত না করা — পরে rank খুঁজতে গিয়ে সেই value list-এ নেই।
  • Update-এ পুরনো salary -1 করতে ভুলে যাওয়া — তাহলে একই কর্মী দুবার গোনা হয়।
  • BIT-এর index-কে কর্মীর position ভাবা — এখানে index মানে value-র rank।

21. Which basic problem this inherits from

ভিত্তি: BIT-as-frequency-table (../fenwick-tree.md section 9) + coordinate compression (10^9 value-কে rank-এ নামানো, এই tracker-এর #13/#14-এও একই reflex)। base BIT-এর runnable code ../implementation.py-তে।

22. Similar harder problems

23. Pattern learned

BIT over compressed values: salary-র মতো বিশাল-range value-কে rank-এ compress করে Fenwick-এ frequency রাখা, তারপর range count = দুটো prefix count-এর বিয়োগ, আর update = এক টোকেন এ-rank থেকে ও-rank-এ সরানো। index মানে value, position নয় — এই চিন্তাটাই counting problem-গুলোর চাবি।

24. Final summary

ভবিষ্যতের আমাকে: "কতগুলো value একটা range-এ, value বদলাতে বদলাতে" দেখলেই BIT-over-values মনে করবে। Value বিশাল হলে আগে compress করো; count জমাও rank-এ; range count = prefix_count(b) - prefix_count(a-1); update মানে পুরনো rank -1, নতুন rank +1। সব O(log n) — prefix-sum subtraction trick-এর সবচেয়ে শক্তিশালী রূপ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।