Difference Array

n সাইজের একটি integer array arr[ ] এর difference array diff[ ] এর i তম element হবে diff[i] = arr[i] - arr[i-1]. যেমন,

arr[ ] = { 12, 9, 91, 20 }

diff[ ] = { 12, -3, 82, -71 }

এই diff[] array এর উপর যদি আমরা prefix sum করি, তবে আমরা arr[] টি পাব। উপরের diff[ ] এর উপর prefix sum করার পর প্রাপ্ত array { 12, 9, 91, 20 }.

এই concept এর উপর আমরা এখন একটি সমস্যার ও এর সমাধান দেখবো। আমাদের একটি n সাইজের integer array a[ ] এবং সাথে q সংখ্যক update query দেওয়া আছে। প্রত্যেক update query তে একটি range [ L, R ] ও একটি integer v দেওয়া আছে। আমাদেরকে  a[L] থেকে a[R] পর্যন্ত সবগুলো element এর সাথে v যোগ করতে হবে। এভাবে সবগুলো update query চালানোর পর আমাদেরকে array টি print করতে হবে। 

প্রতি কুয়েরির জন্য [ L, R ] রেঞ্জের সকল element একটি একটি করে update করে আমরা খুব সহজেই O(q*n) সমাধান লিখতে পারি। কিন্তু আমরা difference array এর concept ব্যবহার করে সমস্যাটি O(q+n) এ সমাধান করতে পারি। সেই সমাধানটি এখন আমরা দেখবো। 

প্রথমেই আমরা একটি লুপ ব্যবহার করে array a[ ] এর difference array diff[ ] বের করে নিবো। আমরা একটু আগেই দেখেছি যে কোন array এর difference array এর উপর prefix sum apply করলে সেই array টি পাওয়া যায়। এখন আমরা এই concept টি কাজে লাগাবো। 

diff[0] = a[0]; for( int i=1; i<n; i++){     diff[i] = a[i] - a[i-1]; }

আমরা প্রত্যেক update query range [ L, R ] এর জন্য diff[L] এর সাথে v যোগ করবো এবং diff[R+1] থেকে v বিয়োগ করবো। এর ফলে ভবিষ্যতে আমরা যখন prefix sum করবো তখন এই অতিরিক্ত যোগ করা অংশ L থেকে R range এর সব element এর সাথে যোগ হয়ে যাবে, যেমনটি আমাদের সমস্যায় চাওয়া হচ্ছে। এভাবে প্রত্যেক update query এর জন্য এভাবে update করার পর diff[ ] array কে prefix sum করলেই আমরা ultimate answer array পেয়ে যাবো। 

for( int i=0; i<numberOfQueries; i++){     int L, R, v;    cin>>L>>R>>v;     diff[L] += v;         if(R+1 < n) diff[R+1] -=v; } for( int i=1; i<n; i++)    diff[i] += diff[i-1];

একই আইডিয়া সামান্য আলাদাভাবে কোড করা যায়। এক্ষেত্রে আমরা given array থেকে difference array বানাবো না। (n+1) size এর একটি integer array d[ ] রাখবো। শুরুতে d[ ] এর প্রতিটি element হবে 0. এবার আগের মতোই প্রত্যেক update query range [ L, R ] এর জন্য d[L] এর সাথে v যোগ করবো এবং d[R+1] থেকে v বিয়োগ করবো। এখন d[ ] এর উপর prefix sum করলে d[i] নির্দেশ করবে given array তে a[i] এর সাথে কত যোগ করলে আমরা ultimate answer array পাবো। 

memset(d, 0, sizeof d); for( int i=0; i<numberOfQueries; i++){     int L, R, v;    cin>>L>>R>>v;     d[L] += v;         if(R+1 < n) d[R+1] -=v; } for( int i=0; i<n; i++)    a[i] += d[i];