Prefix Sum , Prefix XOR

Prefix Sum: মনে কর, তোমাকে একটা অ্যারে দেয়া আছে 10^5 সাইজের। এবং 10^5 সংখ্যক কুয়েরী দেয়া থাকবে। প্রতি কুয়েরী তে left এবং right দুইটা ভ্যারিয়েবল দেয়া থাকবে। বলতে হবে, 

ara[lft] + ara[lft+1] + --- + ara[rgt-1] + ara[rgt] = কত? মানে, left থেকে right তম ইনডেক্স পর্যন্ত সাবঅ্যারে টার যোগফল কত? 

এই কাজটিই আমরা Prefix Sum দ্বারা করতে পারি। যেখানে,

PrefixSum[i] = 1 থেকে i তম ইনডেক্স পর্যন্ত অ্যারের এলিমেন্টগুলোর যোগফল। তাহলে, আমরা লিখতে পারি,

PrefixSum[i] = PrefixSum[i-1] + ara[i]

Sum[l...r] = PrefixSum[r] - PrefixSum[l-1]

Prefix XOR: Prefix XOR টার্মটাও মোটামুটি Prefix Sum এর অনুরূপ। এই প্রব্লেমে আমাকে বার বার কুয়েরী করা হবে left থেকে শুরু করে right পর্যন্ত অ্যারের সংখ্যাগুলোর XOR কত? 

এই কাজটি আমরা করবো Prefix XOR দিয়ে। যেখানে,

PrefixXOR[i] = 1 থেকে i তম ইনডেক্স পর্যন্ত অ্যারের এলিমেন্টগুলোর XOR। তাহলে,

PrefixXOR[i] = PrefixXOR[i-1] ^ ara[i]

XOR[l...r] = PrefixXOR[r] ^ PrefixXOR[l-1]