Prefix, difference ও contribution — তিনটি পূর্ণ ছবি¶
Prefix: [2,4,1,3]¶
Array: index 1 ও 2-এর যোগ চাই
02চিহ্নিত ঘর: 14↑ Lচিহ্নিত ঘর: 21↑ R−133[1,3) range-এ ডানের সীমা 3 বাদ; নিই 4 ও 1।
Prefix: প্রথম kটি মানের যোগ
00চিহ্নিত ঘর: 12↑ L26চিহ্নিত ঘর: 37↑ R410প্রথম 3টির যোগ 7 থেকে প্রথম 1টির যোগ 2 বাদ: উত্তর 5।
[1,3) মানে index 1 ও 2: 4+1=5। Prefix দিয়ে prefix[3]-prefix[1]=7-2=5। খালি prefix রাখায় l=0 হলেও একই সূত্র।
Difference: index 1 থেকে 3 পর্যন্ত +5¶
চারটি শূন্যের array-এ inclusive range [1,3] আপডেট করি। অতিরিক্ত শেষ ঘরটি sentinel।
| index | 0 | 1 | 2 | 3 | 4 (sentinel) |
|---|---|---|---|---|---|
| delta | 0 | +5 | 0 | 0 | −5 |
| চলমান যোগ | 0 | 5 | 5 | 5 | 0 |
ফল [0,5,5,5]। Range-এর শুরুতে +5 চালু, শেষের পরের ঘরে −5 দিয়ে বন্ধ। অনেক update হলে সব delta জমিয়ে শেষে এই একটি pass।
Contribution: [2,4,1]-এর মাঝের 4¶
flowchart TD
V["index 1-এর মান 4"] --> A["[4]"]
V --> B["[2,4]"]
V --> C["[4,1]"]
V --> D["[2,4,1]"]4 আছে চারটি subarray-তে: বাঁ সীমার 2টি × ডান সীমার 2টি পছন্দ। অবদান 16। একইভাবে 2-এর অবদান 2×1×3=6, 1-এর 1×3×1=3; সব subarray sum-এর মোট 6+16+3=25।
যাচাই: ছয়টি subarray-এর যোগ 2,4,1,6,5,7; মোট 25। Minimum-এর contribution-এ এই একই count সরাসরি চলে না—আগের/পরের ছোট মানের boundary চাই।
2D prefix: কেন একবার ফেরত যোগ করি¶
মূল matrix
123চিহ্নিত ঘর: 4শুধু নিচের ডানের ঘর 4-এর যোগ চাই।
Padded prefix
ফাঁকা বা বাদ দেওয়া ঘর: 0ফাঁকা বা বাদ দেওয়া ঘর: 0ফাঁকা বা বাদ দেওয়া ঘর: 0ফাঁকা বা বাদ দেওয়া ঘর: 0চিহ্নিত ঘর: 1চিহ্নিত ঘর: 3ফাঁকা বা বাদ দেওয়া ঘর: 0চিহ্নিত ঘর: 4চিহ্নিত ঘর: 10চারটি সীমার মান নিই: 10 − 3 − 4 + 1 = 4।
শুধু নিচের ডানের 4 পেতে 10−3−4+1=4। ওপরের strip ও বাঁয়ের strip বাদ দিলে 1 দুবার বাদ পড়ে; তাই সেটি একবার ফেরত দিই।
Prefix + frequency: [1,−1,1], target 1¶
| নতুন prefix | খুঁজি prefix−1 | আগে কতবার ছিল? | মোট উত্তর |
|---|---|---|---|
| 1 | 0 | 1 (খালি prefix) | 1 |
| 0 | −1 | 0 | 1 |
| 1 | 0 | 2 | 3 |
প্রথমে freq={0:1}; প্রতিটি ধাপে খোঁজার পরে বর্তমান prefix-এর frequency বাড়াই। তিনটি subarray হলো প্রথম [1], শেষ [1], পুরো [1,−1,1]। Negative থাকলেও এই হিসাব চলে।
Sweep line: একই সময়ে কতটি কাজ চলছে¶
Half-open interval A=[1,4), B=[2,3), C=[4,5)।
| সময় | event | active |
|---|---|---|
| 1 | A শুরু: +1 | 1 |
| 2 | B শুরু: +1 | 2 |
| 3 | B শেষ: −1 | 1 |
| 4 | A শেষ, C শুরু: মোট 0 | 1 |
| 5 | C শেষ: −1 | 0 |
সর্বোচ্চ 2টি একসঙ্গে। Inclusive endpoint-এর প্রশ্নে একই সময়ের start/end-এর নীতি ভিন্ন হতে পারে।