Saturday, February 17, 2018

স্ট্যাক ( Stack )

স্ট্যাক (stack)

ধরি আমি কোন রেস্টুরেন্ট এ কাজ করি। আমার কাজ হচ্ছে থালাবাসন পরিষ্কার করা। এখন আমি এক গাদা প্লেট খাবার টেবিল থেকে নিয়ে ধুবো এবং এরপরে প্লেটগুলি স্তুপ করে একটার উপর একটা রাখবো। এখন লক্ষ্য করলে দেখবে যে প্লেট টা সবার আগে পরিষ্কার করলাম, সেটা কিন্তু স্তুপ এর সবার নিচে আছে। অর্থ্যাৎ আরেকভাবে বললে , যে প্লেট টা সবার পরে পরিষ্কার করলাম সেটা স্তুপ এর সবার উপরে আছে। এখন আমি পরিষ্কার প্লেটগুলি যখন নিবো, তখন কিন্তু স্তুপ এর উপরের থেকেই নেয়া শুরু করবো। অর্থ্যাৎ যে সবার আগে স্তুপ থেকে বের হবে, সে আসলে সবার শেষে স্তুপ এ ঢুকেছিল।

এটি ই স্ট্যাক এর মূল বৈশিষ্ট। একে আমরা বলি “Last In First Out” বা সংক্ষেপে “LIFO”.
এই জিনিসটাকে বলে স্ট্যাক। মানে আমরা সবার পরে যাকে প্রসেসিং করতে ঢুকাচ্ছি তাকে যদি আগে প্রসেসিং করি তাহলে সেটাই স্ট্যাক। STL এ স্ট্যাক ব্যবহার করতে হয় এভাবে,

#include <stack>
using namespace std;
int main()
{
        stack s;  //  একটি ইন্টিজার এর স্ট্যাক
        s.push( 10 );
        s.push( 20 );
        s.push( 30 );
}
/* 10, 20, 30 কে স্ট্যাক এ পুশ করলাম। এখন আমার স্ট্যাক টা দেখতে হবে অনেকটা এরকম
30 // top value of the stack (LIFO)
20
10
*/অর্থাৎ স্ট্যাক এ এখন ৩ টি ভ্যালু আছে।

তাই, স্ট্যাক এর সাইজ হবে ৩।  s.size() এর মাধ্যমে আমরা স্ট্যাক এর সাইজ জানতে পারি।

এখন আমরা স্ট্যাক এর টপ ভ্যালু দেখতে চাইলে যে ফাংশন ব্যবহার করবো তাহলো top() ফাংশন।

int x = s.top();    // x এর মধ্যে স্ট্যাক এর টপ (30) ভ্যালু আছে
cout << x << endl; // x = 30;

এখন যদি আমরা পরের ভ্যালু দেখতে চাই, তাহলে আমাদের আগে টপ এর ভ্যালু কে মুছে ফেলতে হবে। মুছে ফেলার জন্য আমরা ব্যবহার করবো pop() ফাংশন।

s.pop();       // স্ট্যাক এর টপ টাকে ডিলেট করে ফেললাম।
এখন আমার স্ট্যাক এর টপ ভ্যালু হবে 20.

আরেকটা গুরুত্বপুর্ণ ফাংশন হলো empty()
এর কাজ হল স্ট্যাক টা খালি (NULL) আছে কিনা তা চেক করা।
একটি কোড দেখা যাক,

while( !s.empty() )
{
        cout<< s.top() <<endl; // printing the top element;
        s.pop(); // removing the top element;
}
// যতক্ষন স্ট্যাক টা নাল না হবে, ততক্ষন স্ট্যাক এর এলেমেন্ট গুলি প্রিন্ট করলাম

স্ট্যাক দিয়ে আমরা অনেকরকম প্রব্লেম সল্ভ করতে পারি। এর মধ্যে ব্র্যাকেট ম্যাচিং (Bracket Matching or Paranthesis Matching) উল্লেখযোগ্য। তোমরা এগুলো একটু ঘাটাঘাটি করে দেখতে পারো। paranthesis matching নিয়ে পরে কোন এক পোস্ট এ কিছু লিখবো।

ভেক্টর ( Vector )

STL

সি++ এ বিশাল একটি লাইব্রেরী আছে, যার কোডগুলো যেকোন ধরণের ডাটার জন্য কাজ করতে পারে। এই টেম্প্লেট লাইব্রেরীর সবচেয়ে স্ট্যান্ডার্ড ভার্শনটার নামই স্ট্যান্ডার্ড টেম্প্লেট লাইব্রেরী, ওরফে STL।
STL হল একটা বেশ বড়সড় একটা লাইব্রেরী। আমাদের শুধু জানতে হবে সেটা আমরা কিভাবে ব্যবহার করবো। এখন আমরা কিছু STL নিয়ে আলোচনা করবো।

ভেক্টর (vector)

মাঝে মাঝে আমাদের এমন কিছু দরকার হয় যেখানে সাড়ি থাকবে n সংখ্যক, প্রতি সাড়ি তে আবার m সংখ্যক কলাম ও থাকবে। এখানে n,m <= 10000. এবং বলা আছে, কোন কোন সাড়ি তে আবার কলাম নাও থাকতে পারে, মানে ব্যাপারটা এভাবে চিন্তা করলে দেখা যায়, এমন সাড়ি থাকতে পারে যেখানে 10000 এর মতন কলাম আছে, আবার এমন সাড়িও থাকতে পারে যেখানে অনেক কম কলাম আছে। 10000 টা সাড়ি থাকতে পারে যার প্রতিটি মাত্র 5-6 টি কলাম নিয়ে আছে।আর বলা আছে, সাড়ি এবং কলাম মিলে 1000000 এর বেশি কোন ভ্যালু নেই। এখন কথা হল, আমরা যদি এরকম একটা scenario কল্পনা করি তাহলে আমরা 2D (Dimensional ) অ্যারে এর কথা ভাবতে পারি এভাবে,

int a[10000][10000]; // ইনটিজার টাইপ এর একটি অ্যারে, a
এটা কিন্তু বেশ বড়সড় একটা অ্যারে। আমার কম্পিউটার মাথা ঘুরে পড়ে যাবে তাকে এই পরিমান মেমরি অ্যালোকেট করতে বললে, কিন্তু আমার আসলে এত বেশি জায়গা লাগছে না, কারন আমাকে বলেই দেয়া হয়েছে ডাটা সবমিলে সর্বোচ্চ 1000000 টা থাকতে পারে। এধরণের সময়, আমরা ডাইনামিক মেমরি অ্যালোকেট করি - ঠিক যতটুকু মেমরি দরকার ঠিক ততটুকুই নেই। যেটা ম্যানুয়ালি করা বেশ কষ্টকর, আর সেটায় মেমরি পরিষ্কারও করে দিতে হয় কাজ শেষে, নইলে সব ডাটা জমতে জমতে কম্পিউটারের crash করার সম্ভাবনা প্রায় ৮৫% (:P)।
ভেক্টর হলো একটা অ্যারে, যেটায় ডাইনামিকালি জিনিসপাতি ঢুকিয়ে রাখা যায়। মানে, এটাও একটা অ্যারে, কিন্তু সেটা ঠিক ততটুকু মেমরি খায়, যতটুকু খাওয়া লাগে।

ভেক্টর এর হেডার ফাইল ঃ #include<vector>
ভেক্টর ডিক্লেয়ার করে এভাবেঃ  vector< int > a;

যদি অন্য কোন টাইপের ডাটা নিতে চাই তাইলে int এর জায়গায় সেই ডাটার নাম লিখতে হবে। যেমন এটা আরো কিছু অ্যারে।
vector< double > hash;
vector< long long > balti;
vector< char > cow;
vector< float > dalim;

ভেক্টরে কোন ডাটা রাখতে হলে, সেই ভেক্টরের শেষে ডাটাটাকে পুশ করতে হয়।
a.push_back( 100 );       // push_back() function
আর ভেক্টরে কয়টা ডাটা আছে সেটা আমরা জানতে পারি .size() ফাংশনকে কল করে। যেমন আমি একটা ভেক্টরে কিছু ইন্টেজার ঢুকাবো, তারপর সবাইকে প্রিন্ট করবো, সেটার কোড হবে এরকমঃ

int main() {
vector< int > v;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
for( int i = 0; i < v.size(); i++ )
cout << v[i] << endl;
return 0;
}

বাকি সব কিছুতে ভেক্টরকে সাধারণ অ্যারের মত ব্যবহার করা যায়। যেমন আমি 0th এলিমেন্টটা পাল্টে দিতে পারি v[0] = 10000 লিখে। আরেকটা সুবিধা হচ্ছে আমরা অ্যারেতে সরাসরি কপি করতে পারি না । কিন্তু ভেক্টরে সেটা করা যায়ঃ

int main() {
vector< int > v, cp;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
cp = v; // copying
for( int i = 0; i < cp.size();  i++ )
cout << cp[i] << endl;
return 0;
}

ভেক্টরে যদি আমি 2D ডাটা রাখতে চাই তাহলে সেটা দুভাবে করা যায়
vector< int > v[100];
vector< vector< int > > v;

প্রথমটি বেশি preferable, তবে এখানে  row  ১০০ টাই থাকবে,আমি ১ টি row ব্যবহার করলেও প্রোগ্রাম ১০০ টার জন্য জায়গা নিয়ে রাখবে।
পরেরটির কলাম ও ডাইনামিকালি চেঞ্জ করা যাবে।
* vector< vector< int >> v; এভাবে লিখলে >> এর জন্য কিছু কম্পাইলর কিন্তু এরর দিবে।
তাই সাবধানতা অবলম্বন করে spacing ব্যবহার করা ভালো।

সমস্যা
১. ১০ থেকে ১০০০০ এর মাঝের সকল বেজোড় সংখ্যা ভেক্টরের মাঝে নিয়ে প্রিন্ট কর।
২. N সংখ্যক ইন্টিজার এবং k একটি সংখ্যা দেয়া হবে। তোমাকে বলতে হবে k সংখ্যাটি N সংখ্যক                 ইন্টিজার এর মাঝে কতবার আছে?
৩. N সংখ্যক ইন্টিজার কে ছোট থেকে বড় আকারে প্রিন্ট কর।
৪. N সংখ্যক ইন্টিজার দেয়া হবে। প্রতিটি ইন্টিজার কতবার করে আছে (ascending order) প্রিন্ট কর।
Input :
6
10 10 2 3 2 8
Output :
2 is 2 times.
3 is 1 times.
8 is 1 times.
10 is 2 times.

Thursday, February 15, 2018

CodeChef: February Long Challange 2018

Chef And His Characters: Given a string, we need to find four contiguous characters that can make a string "chef". We need to print how many four contiguous characters ('c','e','f','h') we found. If we found any simply write "lovely (the number of contiguous four characters we found)" else print "normal" without the quotes.

Solution:  The easiest problem of the set. Simply bruteforce through the string from 0 to length-4 and each time see if four contiguous characters are found or not. If found, increase the counter. Finally output the result.
Chef and The Patents: Given N patents we need to complete all of them in M months with K workers. Also each worker can work only one patent at most, that is, if we use a worker for a patent, we can't use him anymore. Every single patent needs exactly one month to finish. And we are also given X, that is at most X workers can work in a month. We are finally given a string of length K denoting the workers. On odd month, workers with character 'O' can work and on even month, worker with character 'E' can work.

Solution: It's a greedy problem. Some key things to notice:

  • Worker can work only one month (after working one month, current worker would no longer be available).
  • Restriction in odd and even month.
  • At most X workers can work on a single month.

We just need to calculate for each month, how many workers can be used to finish how many patents. As a single worker can finish single patent at a time and there is a restriction of even and odd month, we will simply iterate through all the months from 1 to M. Then for each month, we will select minimum(number of workers, X). This is the value of the number of patents we can get in a month. In odd month, the number of worker should be the number of 'O' in the string. Similarly for even month the number of workers would be the number of 'E' in the string. Every time we get minimum workers, we will discard that number from that particular type of worker as a worker can at most work 1 month, so he won't be available after he has done his part. We will store the value every time we count how many workers can work in every month, then simply check if the value is >= N or not. If >= N, then 'yes', else 'no'

Permutation and Palindrome: Given a string, we need to make that string a palindrome re-arranging it's characters and output the indices of those characters that made the palindrome string.

Solution: It's a greedy implementation problem. Some key things to notice:

  • If the string length is even and at least one character has odd frequency, we can't make it a palindrome. ex: "aacb"; Here, 'c' and 'b' has frequency = 1, which is odd, and the string length is 4, which is even, so no palindrome can be made.
  • If the string length is odd and at least two character has odd frequency, we can't make it a palindrome. ex: "acccb"; Here, 'a', 'b' and 'c' has frequency 1, 1 and 3 respectively, which is odd and the string length is odd. So we can't make a palindrome.
Now how to make the palindrome. We can simply check all the frequency of the characters. If frequency is even, then we will take first half of the position (index) in our first vector, say X.
And second half will go to vector Y. For even length, we won't have any odd frequency, so we will simply reverse Y and then merge it with X to get final output. For odd we need to get the odd element's index first. let's see for even length:

string = "abababab"
We will push the indices accordingly in a vector containing frequency of each character. So,

vector['a'] = 1 3 5 7
vector['b'] = 2 4 6 8

Now, we will iterate through the character's frequency. For 'a'
The first half will go to vector X, and second half will go to vector Y. So.
X = 1 3
Y = 5 7
Now, for 'b', similarly
X = 1 3 2 4
Y = 5 7 6 8

Now, reverse the Y and merge it with X to get the final result.
Final = 1 3 2 4 8 6 7 5

If we observe the indices, we can make this: "aabbbbaa"; which is a palindrome.}

Similarly, we can make this for odd length. There will be one character with odd frequency. we will take first index of that character from our vector[] array, then everything else follows exactly same.
Before merging Y with X, we need to push that odd frequency index to X first.

Car-pal Tunnel: In this problem we are given N tunnels and each consecutive tunnel has D meter distance. There are C cars each having same velocity S meter per second.
Each tunnel has a toll booth that takes Ai second to process a single car. At the time of processing one car, no car can come to that booth for processing. All the tunnels are linearly connected via these toll booths. We need to calculate the delay time between the first and last car after all of them is processed by all the toll booths.

Solution:
After a bit of observation, we will see that, the maximum time of a toll booth will be the distance between any two cars. So if there are C cars, then the answer will simply be (C-1)*maximum (Ai). Let’s see this case:

3
5 15 8
2 3 1

Here, 3 toll booth which have 5,15,8 second to process each car respectively. We have 2 cars each having velocity 1 meter per second. Each tunnel has 3 meter distance. So for a single car to cross a tunnel, it needs 3/1 = 3 second. Now let’s see, when the first car is being processed at the first booth, after 5 second, it will go out from the booth and second car will start processing. 
  • 1 second goes, first car moves 1 meter, second car’s process time is also 1 sec.
  • 2 second goes, first car goes 1 meter, second car’s process is 2 second.
  • 3 second goes, first car is now at second booth for processing, second car’s 3 sec processing time is finished at first booth.
 So the distance between two cars will be 3 second.

Now, after 4,5,6 second, the second car will arrive at the second booth, but the first car is still being processed at that booth. So the second car will stop there. So our delay is now updated to 15 second,
as we clearly know, after processing of the first car (which will take 15 second for 2nd booth) only then the second car can start processing. So the distance between them will be then 15 second. So the answer is 15*(2-1) = 15; [15 is the maximum toll booth time for a particular booth].

This observation is correct when C is equals to two. If there are more cars, then we need to keep the distance is calculation too. The delay is D/S for every car that takes D/S second to pass D meter distance. But if we happen to come to any case where D/S is greater than maximum of toll booth time, then we need to take the maximum (D/S, toll booth time). Notice this is applicable when there are cars more than two. If only two car is present, then maximum of toll booth is the correct solution.


Sunday, February 11, 2018

LightOJ: Points in Rectangle


Problem link: loj 1266

Technique: Binary Indexed Tree

If you don't know about Binary Indexed Tree, first learn it. You can also check BIT here BIT

Given two types of query,
  • 0 x y: we got a new point at co-ordinate (x,y) [ if already a point exist in the same co-ordinate, this query does nothing ] 
  • 1 x1 y1 x2 y2: we are given a rectangle whose lower left co-ordinate is (x1, y1) and upper-right corner is (x2, y2); your task is to find the number of points, given so far, that lie inside this rectangle. You can assume that (x1 < x2, y1 < y2).
We will maintain a 2-D BIT(Binary Indexed Tree) to solve this problem. For query 0 x y, we will call update function each time we got a new point (x,y). For the second query, we will call out query_sum function with parameter (x,y); it means we will get the sum of the rectangle that's lower left co-ordinate is (1,1) and upper right co-ordinate is (x,y). Let's see a testcase:

1
4
0 1 1
0 2 6
1 1 1 6 6
1 2 2 5 5

We got two points (1,1) and (2,6), let's plot these points:


Now let's see the first query, we have to find how many points are inside (1,1) and (6,6). We will call out query_sum function with parameter (6,6), And this will cover the whole area from (1,1) to (6,6) and we will get output = 2
Ok, for the second query we need to find points inside (2,2) and (5,5). We will call our query_sum function with (5,5) and the selected area would be like this:


But we have some extra area here as our query starts from (2,2). So we need to remove those extra area. Basically we need to calculate our desired area as follow:

area = query_sum(x2,y2)-query_sum(x1-1,y2-1)-query_sum(x2-1,y1-1)+query_sum(x1-1,y1-1)

Let's see how does it look, Here:
A = query_sum(x2,y2)
B = query_sum(x1-1,y2-1)
C = query_sum(x2-1,y1-1)
D = query_sum(x1-1,y1-1)

     
 


We added D because, while subtracting B and C, D got subtracted twice. So we need to balance it by adding. Hope you understand what we need to do here.

Code:

বাইনারি ইন্ডেক্সড ট্রি অথবা ফেনউইক ট্রি ( Binary Indexed Tree or Fenwick Tree )

কোন অ্যারের সংখ্যাগুলোর যোগফল বের করতে, কোন ইনডেক্স আপডেট করতে আমরা বাইনারি ইন্ডেক্সড ট্রি ব্যবহার করি। এসব কাজ আমরা সেগমেন্ট ট্রি দিয়েও করতে পারি, কিন্তু Binary Indexed Tree (BIT) দিয়ে কোড করা অনেক সহজ এবং খুব দ্রুত কোড করে ফেলা যায়। আসলে এই BIT ঠিক কি কাজে লাগে? 
  • কোন অ্যারের 0 থেকে N পর্যন্ত যোগফল, মিনিমাম, ম্যাক্সিমাম ইত্যাদি বের করা
  • কোন ইন্ডেক্স আপডেট করা
লক্ষ্য রাখতে হবে যে, BIT দিয়ে আমরা 0 থেকে যেকোন রেঞ্জ এর কিছু অপারেশন ক্যাল্কুলেট করবো। এখানে আমরা 1 বেস ইনডেক্স নিয়ে আলোচনা করবো।
আমরা নরমালি যোগফল লুপ চালায়ে বের করতেই পারি, কিন্তু BIT আমাদের এই কাজকে O(logN) এ করে দেয়।

BIT শুরু করার আগে একটু bit নিয়ে কাজ করা যাক। 

আমরা যেকোন একটি নম্বর এর সর্বশেষ সেট(1) বিটকে সরানোর চেষ্টা করি, কেন করছি, তা পরে বলি।
ধরি, একটি নম্বর = 14. একে বাইনারি তে নিলে হবে = 1110 (যেহেতু বিট এর হিসাব সব বাইনারিতে হয়, আমরা বাইনারি নিয়ে বেশি মাথা ঘামাবো)
এখন এই 1110 এর সর্বশেষ সেট বিট হচ্ছে 1 নং পজিশন এ।
এখন আমাদের কাজ হল এই 1 পজিশন এর বিট 1 কে সরানো। আমরা এটি করতে পারি এভাবেঃ x & (-x)
এখানে x = 14; অর্থাৎ আমরা একটি অ্যান্ড অপারেশন এর মাধ্যমে এটি করতে পারি।
x = 14 = 1110
x = -14 = 0010
x & (-x) = 1110 & 0010 = 10 (আমরা এভাবে সর্বশেষ সেট বিট কে আলাদা করে ফেললাম)

এখন কথা হচ্ছে, কেন আমরা এভাবে আলাদা করে ফেললাম? একটু পরেই আমরা বুঝতে পারবো। এখন আমরা সরাসরি BIT এর মাঝে চলে যাবো।

বাইনারি ইন্ডেক্সড ট্রি ( Binary Indexed Tree )


আমরা জানি, যেকোন সংখ্যা কে ২ এর পাওয়ারের যোগফল আকারে লিখা যায়। আমরা ধরে নেই আমাদের একটি অ্যারে আছে যার নাম BIT অ্যারে। এখানে আমরা যেকোন ইনডেক্স এ অ্যারের কিছু সংখ্যার যোগফল রাখবো। অর্থাৎ এটি আমাদের একটি পারশিয়াল সাম ট্রি হিসাবে কাজ করবে।
ধরি আমাদের একটি অ্যারে আছে A[ ]. এবং আমাদের partial sum সেভ করে রাখার জন্য আছে BIT[ ] অ্যারে। ধরি আমাদের A[ ] অ্যারের ইনডেক্স ১ বেসড। এখনঃ
A [ ] = { 1, 2, 3, 4, 5, 6 }
এবং আমাদের BIT অ্যারে হবে এরকমঃ

BIT [ 1 ] = A [ 1 ] = 1
BIT [ 2 ] = A [ 1 ] + A [ 2 ] = 1 + 2 = 3
BIT [ 3 ] = A [ 3 ] = 3
BIT [ 4 ] = A [ 1 ] + A [ 2 ] + A [ 3 ] + A [ 4 ] = 10
BIT [ 5 ] = A  [5 ] = 5
BIT [ 6 ] = A [ 5 ] + A [ 6 ] = 11

এটি একটি বাইনারি ইন্ডেক্সড ট্রি এবং BIT [ index ] এর মাঝে আমাদের A অ্যারের partial sum সেভ করা আছে।
অর্থাৎ,

BIT [ n ] =   A [ n ] ; if n is odd
                     A [ 1 ] + A [ 2 ] + ... + A [ n ]; if n is power of 2

আমরা প্রতিবার আমাদের BIT অ্যারেকে আপডেট করার মাধ্যমে ভ্যলুগুলি জেনারেট করবো। প্রতিবার আমরা A অ্যারের প্রতি ইনডেক্স এর জন্য আমাদের update(int index,int value) call করবো।
এখন প্রশ্ন আসতে পারে, যদি n এর মান বিজোড় কিংবা 2 এর পাওয়ার না হয়, তাহলে আমরা কি করবো? আমরা জানি যেকোন নম্বরকে 2 এর পাওয়ার হিসেবে লিখা যায়। আমাদের আপডেট ফাংশন 2 এর পাওয়ার না পেলে, তার ঠিক পরের 2 এর পাওয়ার পর্যন্ত ভ্যালুকে আপডেট করতে থাকবে। হাতে কলমে সিমুলেশন চালায়ে ব্যাপারটি দেখতে পারেন আপনারা।


ধরি আমরা update(5,2) call করলাম। এরমানে হচ্ছে, আমরা 5 ইনডেক্স কে 2 দিয়ে আপডেট করবো।
এখন, 5 = 101, BIT [ 5 ] += 2
আমাদের BIT [ 6 ] এও আপডেট করতে হবে, কাজেই আমরা যখন index & (-index) ব্যবহার করবো,
101 & 011 = 1; যা কিনা দশমিক এ 1। কাজেই আমরা 1 বারিয়ে দিব আমাদের কারেন্ট ইনডেক্স এর মান, এবং নতুন ইনডেক্স পাবো 6, কাজেই BIT [ 6 ] += 2 করে দিবো। এরপরে আমরা আবার একই কাজ করবো,
110 & 010 = 10; দশমিক এ ২, কাজেই নতুন ইনডেক্স = 6+2 = 8; কিন্তু 8 > 6, কারন আমরা A আ্যরের সাইজ নিয়েছি 6. এভাবে আমাদের আপডেট ফাংশন কাজ করে।

এখন কুয়েরি অপারেশন দেখা যাক।

এখানে 1 থেকে index পর্যন্ত সংখ্যার যোগফল রিটার্ন করবে এই কুয়েরি ফাংশন। যেখা যাক কিভাবে কাজ করে,
আমরা 1 to 4 যোগফল চাই, তাহলে query_sum( 4 ) call করবো।
sum = 0
sum += BIT [4] = 0 + 10 = 10
4 = 100
so, 100 & 100 = 100 = 4 (decimal)
so index = index - 4 = 4 - 4 = 0 ; finally return sum;

আপডেট এবং কুয়েরি ২ ক্ষেত্রেই আমরা প্রতিটি ইনডেক্স এর বিট নিয়ে কাজ করছি, কাজেই উভয়খেত্রে আমাদের কমপ্লেক্সিটি O(logN)

কোডঃ



এতক্ষন আমরা দেখলাম 1-D অ্যারের মাঝে যোগফল বের করা। আমাদের যদি 2-D অ্যারের মাঝে এরকম কোন কিছু করতে বলা হয়? তাহলে আমরা কিভাবে আপডেট এবং কুয়েরি চালাবো? ব্যাপারটি খুবি সোজা, যেভাবে আমরা 1-D এর জন্য করেছি, একই কাজ আমরা 2-D এর জন্যেও করবো ২ বার করে। বেশি কিছু না বলে কোড দেখা যাকঃ

এখানে i&(i+1)-1 এবং i|(i+1) দেখে ভয় পাবার কিছু নেই। আমরা এতক্ষন যা করেছি বিট দিয়ে, এখানেও তাই করা হয়েছে। একটু নিজে ঘাটাঘাটি করে দেখার অনুরোধ রইল।


প্র্যাকটিস প্রব্লেম ( Practice Problems )