এই বিভাগে আমরা দেখব সেগমেন্ট ট্রি কি। এটি আলোচনা করার আগে, আসুন একটি সমস্যা দেখি।
ধরুন আমাদের একটি অ্যারে অ্যারে [0,…,n-1] আছে, আমরা নিম্নলিখিত অপারেশনগুলি করতে পারি -
-
সূচী l থেকে r পর্যন্ত উপাদানগুলির সমষ্টি খুঁজুন, যেখানে 0 ≤ l ≤ r ≤ n-1
-
অ্যারের একটি নির্দিষ্ট উপাদানের মান একটি নতুন মান x এ পরিবর্তন করুন। আমাদের arr[i] =x করতে হবে। i রেঞ্জ 0 থেকে n – 1।
আমরা সেগমেন্ট ট্রি ব্যবহার করে এই সমস্যার সমাধান করতে পারি। সেগমেন্ট ট্রি আমাদেরকে O(log n) সময়ে যোগফল এবং প্রশ্ন পেতে সাহায্য করতে পারে। তাহলে আসুন দেখি কিভাবে এই −
কে উপস্থাপন করা যায়-
লিফ নোড হল প্রদত্ত অ্যারের উপাদান
-
প্রতিটি অভ্যন্তরীণ নোড কিছু লিফ নোড একত্রিত প্রতিনিধিত্ব করা হয়. একত্রীকরণ বিভিন্ন ক্ষেত্রে ভিন্ন হতে পারে। এখানে একত্রিত করা হল একটি নোডের নীচে পাতার সমষ্টি৷
ধরুন আমাদের একটি অ্যারে আছে যেমন [1, 3, 5, 7, 9, 11]। তাই সেগমেন্ট ট্রি হবে
