একটা array a[] দেওয়া আছে। এখানে আমাদের কিছু query করতে হবে, যেখানে array এর সাইজ >= ১০৫ এবং query ও করতে হবে ১০৫ এর মতো।
এখানে query গুলো হচ্ছে এমন -
i. set(i, v) => a[i] = v // replace value in 'i'th position with value 'v'
ii. sum(l, r) => a[l] + a[l+1] + a[l+2] + ... + a[r]
তো বুঝাই যাচ্ছে O(nlogn) / O(n) solution লিখতে হবে।
আর এর জন্য খুব সুন্দর একটা ডাটা স্ট্রাকচার আছে - সেগমেন্ট ট্রী!!!
Source: Link
Code:
FAQ: Where we can use Segment Tree?
Answer: যদি উপরোক্ত এর ন্যায় query থাকে এবং associative operation করতে বলা হয়/করা যায় তখন আমরা Segment Tree ব্যবহার করতে পারবো।
Associative Operation: (x + y) + z = x + (y + z)
আরো কিছু উদাহরণ : + (add), * (multiplication), | (bit-wise OR), & (bit-wise AND), ^ (bit-wise XOR), gcd, min, max etc...
** কিছু ক্লাসিকাল প্রব্লেম নিচে দেওয়া হল :
i. Find the maximum element in a range (l, r).
ii. Find the maximum element and its occurrence in (l, r)
iii. Compute GCD / LCM in range (l, r) [O(nlog2n)]
iv. Finding sub-segments with maximum sum in range (l, r)
v. Find kth zero/one in a binary array [also PBDS can be used]
vi. Find first element greater than x in range (l, r)
vii. Given a permutation P of n numbers, find for each i the number of j such that j < i & Pi > Pj
viii. Now for each i the number of j is given, restore the permutation P.
ix. Given an array of 2n elements where 1 to n each occurs exactly twice, find numbers of nested segment for each element.
x. Find numbers of intersecting segments.
[চলিত...]
No comments:
Post a Comment