001 — Static Range Sum Queries¶

Source¶

Original source: CSES Problem Set — Range Queries section
Platform: CSES — https://cses.fi/problemset/task/1646
Topic: segment tree and fenwick tree (warm-up — আসলে tree-ই লাগে না)
Difficulty: Easy
Pattern: prefix sums (frozen array, কোনো update নেই)
Basic idea inherited from: math level 5 prefix sums — ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/

1. Problem in simple words¶

তোমাকে n-টা সংখ্যার একটা array দেওয়া আছে, আর q-টা প্রশ্ন। প্রতিটা প্রশ্নে দুটো index a আর b দেওয়া থাকে, তোমাকে বলতে হবে a থেকে b পর্যন্ত (দুই প্রান্ত সহ) সব element-এর sum কত। গুরুত্বপূর্ণ ব্যাপার: array কখনো বদলায় না — এটা পুরোপুরি frozen।

array = [3, 2, 4, 5, 1, 1, 5, 3]   (1-indexed CSES-এ)
query a=2, b=4  ->  2 + 4 + 5 = 11
query a=5, b=6  ->  1 + 1     = 2

2. Which basic idea does this inherit from?¶

এটা সরাসরি prefix sums-এর উপর দাঁড়িয়ে — তুমি যেটা ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-এ শিখেছ। মূল চিন্তা ছিল: একই যোগ বারবার না করে, "শুরু থেকে প্রতিটা জায়গা পর্যন্ত মোট" একবার লিখে রাখো, তারপর যেকোনো range-এর sum হয়ে যায় একটা বিয়োগ।

3. What is the hidden math or logic?¶

লুকানো logic হলো invertibility: sum একটা invertible operation, মানে যোগকে বিয়োগ দিয়ে undo করা যায়। যদি P[i] মানে প্রথম i-টা element-এর মোট হয়, তাহলে sum(a..b) = P[b] - P[a-1]। বাঁ দিকের অপ্রয়োজনীয় অংশটা ঠিক বিয়োগ করে সরিয়ে দিলেই বাকি থাকে যা চাই।

4. Which data structure is needed?¶

শুধু একটা prefix-sum array। এখানে এই topic-এর নাম "segment tree and fenwick tree" হলেও, এই problem-এ কোনো tree লাগবেই না — কারণ array frozen, কোনো update নেই।

5. Why this data structure fits¶

Tree-গুলোর পুরো অস্তিত্বই update সামলানোর জন্য। যখন কোনো update নেই, তখন একটা plain prefix-sum array-ই সবচেয়ে দ্রুত (build O(n), প্রতি query O(1)) আর সবচেয়ে সরল। Frozen array-র উপর segment tree বানানো spirit-এ ভুল উত্তর — pass করলেও over-engineering।

6. Real-life analogy¶

একটা দোকানদার ভাবো, যে দিনের শেষে খাতায় চলমান মোট (running total) লিখে রাখে: "1 নম্বর ক্রেতার পর মোট কত, 2 নম্বরের পর কত..."। এবার যে-ই জিজ্ঞেস করুক "3 থেকে 7 নম্বর ক্রেতার মোট কত", সে শুধু "7-এর পর মোট" থেকে "2-এর পর মোট" বিয়োগ করে — খাতা আবার ঘেঁটে যোগ করতে হয় না।

7. Visual explanation¶

a = [3, 2, 4, 5, 1, 1, 5, 3]-এর জন্য prefix array P (sentinel P[0]=0 সহ):

index :   0   1   2   3   4   5   6   7   8
a     :       3   2   4   5   1   1   5   3
P     :   0   3   5   9  14  15  16  21  24
              cumulative total up to each position

query a=2, b=4:
        P = [0, 3, 5, 9, 14, 15, 16, 21, 24]
                 ^cut here    ^take here
        sum = P[4] - P[1] = 14 - 3 = 11
        (= 2 + 4 + 5, correct)

লক্ষ্য করো: কোনো tree নেই, শুধু একটা ফিতা থেকে বাঁ দিকের টুকরো কেটে ফেলা।

8. Example input and output¶

Input:
  n = 8, q = 2
  array = [3, 2, 4, 5, 1, 1, 5, 3]
  query 2 4
  query 5 6
Output:
  11
  2

Edge case 1 (পুরো array): a=1, b=8  -> 24
Edge case 2 (একটা element): a=3, b=3 -> 4

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা query-র জন্য a থেকে b পর্যন্ত একটা loop চালিয়ে যোগ করো।

for each query (a, b):
    s = 0
    for i in range(a, b+1):
        s += array[i]
    print(s)

10. Why brute force is slow¶

প্রতিটা query সর্বোচ্চ n-টা element ছোঁয়, আর query আছে q-টা — তাই worst case O(n × q)। CSES-এ n আর q দুটোই 2×10^5 পর্যন্ত হতে পারে, মানে প্রায় 4×10^10 operation — অনেক ধীর, time limit exceed করবে। একই অংশ বারবার যোগ করাটাই অপচয়।

11. Key observation¶

মূল observation: range sum মানেই দুটো prefix sum-এর বিয়োগ। sum(a..b) = (1 থেকে b পর্যন্ত মোট) − (1 থেকে a−1 পর্যন্ত মোট)। একবার সব prefix সাজিয়ে রাখলে, প্রতিটা query একটামাত্র subtraction।

12. Optimized intuition¶

শুরুতেই একবার O(n)-এ prefix array বানিয়ে নাও। তারপর প্রতিটা query-তে শুধু P[b] - P[a-1] return করো — O(1)। মোট খরচ O(n + q), যা brute force-এর O(n × q)-এর তুলনায় আকাশ-পাতাল তফাত।

13. Thinking tweak¶

মোচড়: "প্রতিবার নতুন করে যোগ করব" ভাবার বদলে ভাবো "একবারই সব checkpoint লিখে রাখব, তারপর প্রতিটা উত্তর = দুই checkpoint-এর তফাত।" এই precompute-then-subtract চিন্তাটাই পুরো range-query জগতের ভিত — segment tree আর Fenwick tree এই একই চিন্তাকেই update-সহ্য করার মতো করে বানায়।

14. Step-by-step dry run¶

Array [3, 2, 4, 5, 1, 1, 5, 3], query (2, 4):

Prefix বানাও: P = [0, 3, 5, 9, 14, 15, 16, 21, 24]
Query (a=2, b=4) এসেছে।
P[b] = P[4] = 14
P[a-1] = P[1] = 3
উত্তর = 14 - 3 = 11 → এটাই 2 + 4 + 5, ঠিক আছে।

15. Python solution¶

class PrefixSum:
    """Frozen array-র জন্য O(1) range sum। কোনো tree লাগে না —
    update নেই বলেই plain prefix sums-ই যথেষ্ট আর দ্রুততম।"""

    def __init__(self, data):
        # P[i] = প্রথম i-টা element-এর sum; P[0] = 0 sentinel
        self.P = [0] * (len(data) + 1)
        for i, v in enumerate(data):
            self.P[i + 1] = self.P[i] + v

    def range_sum_1indexed(self, a, b):
        # CSES-style: 1-indexed inclusive [a, b]
        return self.P[b] - self.P[a - 1]


def brute(data, a, b):
    # 1-indexed inclusive, obviously-correct reference
    return sum(data[a - 1:b])


# ---- tests ----
data = [3, 2, 4, 5, 1, 1, 5, 3]
ps = PrefixSum(data)

assert ps.range_sum_1indexed(2, 4) == 11      # 2 + 4 + 5
assert ps.range_sum_1indexed(5, 6) == 2       # 1 + 1
assert ps.range_sum_1indexed(1, 8) == 24      # পুরো array
assert ps.range_sum_1indexed(3, 3) == 4       # একটা element

# brute force-এর সাথে exhaustively মিলিয়ে দেখা
for a in range(1, len(data) + 1):
    for b in range(a, len(data) + 1):
        assert ps.range_sum_1indexed(a, b) == brute(data, a, b)

print("সব test pass!")

16. Line-by-line code explanation¶

self.P = [0] * (len(data) + 1) — n+1 ঘরের array, P[0]=0 sentinel যাতে a=1-এও P[a-1]=P[0] কাজ করে।
self.P[i + 1] = self.P[i] + v — running total: আগের মোটের সাথে এই element যোগ।
range_sum_1indexed(a, b) — P[b] - P[a-1], একটামাত্র subtraction, O(1)।
brute — slow কিন্তু স্পষ্টভাবে সঠিক reference, যেটা দিয়ে fast version verify করা হয়।

17. Output walkthrough¶

PrefixSum([3,2,4,5,1,1,5,3]) বানায় P = [0,3,5,9,14,15,16,21,24]। range_sum_1indexed(2,4) দেয় 14-3=11, (5,6) দেয় 16-14=2 — সব assert pass। double loop সব সম্ভাব্য (a,b)-কে brute force-এর সাথে মিলিয়ে দেখে। শেষে print: সব test pass!।

18. Time complexity¶

Build O(n) (একবার prefix array), প্রতি query O(1) (একটা subtraction)। মোট O(n + q)।

19. Space complexity¶

O(n) — শুধু n+1 ঘরের prefix array।

20. Common mistakes¶

P[b] - P[a] লেখা P[b] - P[a-1]-এর বদলে — তাহলে a নম্বর element বাদ পড়ে যায়।
Sentinel P[0]=0 ভুলে যাওয়া — তখন a=1-এ P[a-1] index ভুল হয়।
Frozen array-তে segment tree বানানো — কাজ করবে, কিন্তু অপ্রয়োজনীয়; update না থাকলে tree লাগে না।

21. Which basic problem this inherits from¶

ভিত্তি: math level 5-এর prefix sums (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)। ঠিক ওই precompute-then-subtract চিন্তা, কোনো নতুন structure ছাড়াই।

22. Similar harder problems¶

Range Sum Query — Immutable (class-based একই idea) — https://leetcode.com/problems/range-sum-query-immutable/ (এই tracker-এর #2)
Range Sum Query — Mutable (এবার update আসে, তাই tree লাগে) — https://leetcode.com/problems/range-sum-query-mutable/ (#5)
Dynamic Range Sum Queries (contest version with updates) — https://cses.fi/problemset/task/1648 (#6)

23. Pattern learned¶

Prefix sums baseline: frozen array-তে range sum = দুই prefix-এর তফাত, O(1) per query। এটাই সেই baseline যার ব্যর্থতা (update এলেই ভেঙে পড়ে) থেকে segment tree আর Fenwick tree-র জন্ম।

24. Final summary¶

ভবিষ্যতের আমাকে: যেকোনো range-query দেখলেই প্রথমে জিজ্ঞেস করো "update আছে কি?"। যদি না থাকে — prefix sums, ব্যস, tree বানিয়ে সময় নষ্ট কোরো না। এই decision drill-টাই এই পুরো folder-এর প্রথম শিক্ষা: ঠিক যেটুকু দরকার, ঠিক ততটুকু structure।

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