Visualization Ideas — Prefix, Difference, Contribution¶
এই level-এর কৌশলগুলো geometry-র মতো — ফিতা, দাগ, rectangle। ছবি ছাড়া এগুলো মুখস্থ formula, ছবিসহ এগুলো সাধারণ জ্ঞান। প্রতিটা concept-এর আঁকার idea, আর শেষে 3টা worked ASCII example।
প্রতি concept-এর visualization idea¶
1. Prefix sum = মাইলফলকওয়ালা রাস্তা¶
Array-টা একটা রাস্তা; প্রতিটা element এক-একটা অংশের দৈর্ঘ্য। P[i] হলো i নম্বর মাইলফলকে লেখা "শুরু থেকে এতদূর এসেছ"। দুই ফলকের মধ্যের দূরত্ব = দুটো লেখা সংখ্যার বিয়োগ — কাউকে রাস্তা মাপতে হয় না। আঁকো: নিচে array-র বাক্স, উপরে ফলকগুলোতে cumulative সংখ্যা।
2. Range sum = ফিতা কাটা¶
পুরো ফিতার দৈর্ঘ্য P[r+1], বাঁয়ের বাড়তি টুকরো P[l] — কাঁচি চালাও, মাঝেরটাই উত্তর। P[l] কাটছ, P[l+1] না — কারণ l-তম element-টা রাখতে চাই। Off-by-one সন্দেহ হলেই এই ফিতার ছবি আঁকো।
3. Difference array = রাস্তার টোল-সাইনবোর্ড¶
Range update মানে রাস্তায় দুটো সাইনবোর্ড পোঁতা: l-এ "এখান থেকে +x" আর r+1-এ "এখানে +x শেষ"। হাজারটা গাড়ি (element) মাঝ দিয়ে যাক — বোর্ড দুটোই। শেষে এক pass হাঁটা (prefix) — প্রতি জায়গায় চালু থাকা টোলের মোট। আঁকো: timeline-এ তীরচিহ্ন দিয়ে +x শুরু/শেষ।
4. 2D prefix = ছবির ফ্রেম কাটা¶
বড় ছবি থেকে ভেতরের একটা rectangle কাটতে চাও: পুরো ছবি − উপরের পট্টি − বাঁয়ের পট্টি + কোণার ব্লক (যেটা দুবার কাটা পড়েছিল)। চার রঙে চারটা rectangle আঁকো — কোণার overlap-টা যেখানে দুই রঙ মিশেছে, সেখানে "+1 বার ফেরত" লেখো।
5. Subarray sum = K = পুরোনো খাতায় খোঁজা¶
Number line-এ prefix-এর মানগুলো দাগাও। r-এ দাঁড়িয়ে তুমি জানো নিজের উচ্চতা P[r]; খুঁজছ এমন পুরোনো বিন্দু যার উচ্চতা ঠিক K কম। Hash map হলো সেই পুরোনো খাতা — "উচ্চতা h কতবার দেখেছি"। প্রতি ধাপে: এক নজর খাতায়, তারপর নিজের উচ্চতা খাতায় টুকে রাখা।
6. Contribution = বাঁয়ে-ডানে পছন্দের গুণ¶
a[i]-কে মাঝে রেখে বাঁয়ে i + 1টা সম্ভাব্য শুরু-বিন্দুতে টিক দাও, ডানে n - iটা শেষ-বিন্দুতে। যেকোনো বাঁ-টিক × যেকোনো ডান-টিক = একটা subarray। দুটো ভাঁজ-করা পাখার ছবি — বাঁ পাখার পাতা × ডান পাখার পাতা।
7. Sweep line = দরজার কাউন্টার¶
অনুষ্ঠানের দরজায় কাউন্টার: কেউ ঢুকলে +1, বেরোলে -1। ঘটনাগুলো সময় অনুযায়ী sort করে পরপর চাপো — কাউন্টারের সর্বোচ্চ reading-ই "একসাথে সর্বাধিক কতজন"। আঁকো: timeline-এ উপরে ↑(+1) নিচে ↓(-1) তীর, নিচে running count-এর সিঁড়ি-রেখা।
Worked ASCII example 1: prefix build আর range query¶
a = [ 2 ] [ 5 ] [ 1 ] [ 3 ] [ 4 ]
ফলক: 0 2 7 8 11 15
P[0] P[1] P[2] P[3] P[4] P[5]
query: sum(1..3) — মানে 5 + 1 + 3
পুরো ফিতা (0..3) : P[4] = 11
বাঁয়ের টুকরো (0..0): P[1] = 2
────────────
উত্তর : 11 - 2 = 9 ✓
P[1] কাটলাম (l = 1-এর ঠিক আগ পর্যন্ত), P[2] না — নইলে 5-টাও কাটা পড়ত।
Worked ASCII example 2: difference array-তে দুটো update¶
n = 6, শুরুতে সব 0। update গুলো:
(1) l=1, r=4, x=+3 (2) l=3, r=5, x=+2
index : 0 1 2 3 4 5 (6)
update1: +3 -3 ← diff[1]+=3, diff[5]-=3
update2: +2 -2 ← diff[3]+=2, diff[6]-=2
diff : [ 0, +3, 0, +2, 0, -3, -2]
হাঁটা (running prefix):
running: 0 → 3 → 3 → 5 → 5 → 2
a = [0, 3, 3, 5, 5, 2] ✓
হাতে মিলাও: index 3-এ দুটো update-ই লাগে → 3 + 2 = 5 ✓
লক্ষ করো diff-এর দৈর্ঘ্য n+1 — r+1 = 6 লেখার জায়গা না থাকলে index error।
Worked ASCII example 3: contribution গোনা (a = [1, 2, 3])¶
n = 3। প্রতিটা i-এর জন্য (শুরু-option) × (শেষ-option):
i=0 (মান 1): শুরু {0} শেষ {0,1,2} → 1 × 3 = 3 বার
i=1 (মান 2): শুরু {0,1} শেষ {1,2} → 2 × 2 = 4 বার
i=2 (মান 3): শুরু {0,1,2} শেষ {2} → 3 × 1 = 3 বার
মোট sum = 1×3 + 2×4 + 3×3 = 3 + 8 + 9 = 20
যাচাই — 6টা subarray সরাসরি:
[1]=1 [2]=2 [3]=3 [1,2]=3 [2,3]=5 [1,2,3]=6 → মোট 20 ✓
কে কয়বার এল: 1 আছে [1],[1,2],[1,2,3] → 3 বার ✓
2 আছে [2],[1,2],[2,3],[1,2,3] → 4 বার ✓
দুটো পথ, একই উত্তর — কিন্তু contribution পথটা O(n), অন্যটা O(n²)।
নিজে practice করার নিয়ম¶
- প্রতিটা prefix problem-এ আগে ফলকসহ রাস্তার ছবি আঁকো, তারপর code — off-by-one bug অর্ধেক কমে যাবে
- Difference array-র dry run টেবিল (index | diff | running) হাতে বানাও — অন্তত দুটো overlap করা update দিয়ে
- 073-এর hash map-এর প্রতি step-এ
seen-এর ভেতরটা লিখে ফেলো — "খাতায় কী আছে" চোখে না দেখলে bug ধরা কঠিন - Contribution-এর বাঁ-ডান পাখার ছবি নতুন array-তে (যেমন 4 element) আবার আঁকো —
(i+1)(n-i)তখন আর formula থাকবে না, ছবি হয়ে যাবে