Prefix Sum

আগে একবার পুরো list দেখে রাখুন, তাহলে পরের প্রতিটা প্রশ্নের উত্তর হবে মাত্র একটা subtraction।

মূল ধারণা

ভাবুন একটা bank statement, যেখানে প্রতিটা transaction-এর পর running balance লেখা আছে। 3 নম্বর থেকে 6 নম্বর transaction-এর মধ্যে কত খরচ হয়েছে? খরচগুলো আবার যোগ করতে হবে না: 6 নম্বরের পরের balance থেকে 3 নম্বরের আগের balance বিয়োগ করলেই হবে।

একটা prefix sum array p হলো ঠিক সেই running balance: p[i] হলো প্রথম iটা সংখ্যার যোগফল। তখন nums[l..r]-এর যোগফল হয় p[r+1] − p[l]। আমরা একটা বাড়তি slot p[0] = 0 রাখি (কিছু না থাকলে যোগফল 0), যাতে l 0 হলেও formula কাজ করে।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Build: O(n) time একবারই লাগে। প্রতিটা query: O(1)। Space: prefix array-র জন্য O(n)। এটা না থাকলে প্রতিটা query-তে n পর্যন্ত সংখ্যা আবার যোগ করতে হতো (প্রতিটায় O(n))।