სეგმენტური ხე: განსხვავება გადახედვებს შორის

== სტრუქტურა და იმპლემენტაცია ==
სეგმენტური ხის ფესვში მოცემულია მთლიანი მასივის შესახებ ინფორმაცია, ანუ <math>[1..n]</math> (<math>n</math> - მასივის ზომა), მის მარცხენა შვილში <math>[1..n / 2]</math>, მარჯვენაში <math>[n / 2 + 1, n]</math> და ასე შემდეგ. შევნიშნოთ, რომ სეგმენტი ორ ნაწილად იყოფა. თუ სეგმენტის ზომა კენტია, არ აქვს მნიშვნელობა მარჯვენაში იქნება მარცხენაზე ერთით მეტი ზომის მქონე სეგმენტი - თუ პირიქით. სეგმენტური ხის ფოთლები, მარცხნიდან მარჯვნივ წარმოადგენენ მასივის ელემენტებს, რადგან ბოლოში მაქსიმალურად დაყოფილი, ანუ ერთ ელემენტიანი სეგმენტებია.
[[ფაილი:Segment_tree.svg|მინი| სეგმენტურის ხის სტრუქტურის გრაფიკული მაგალითი ]]განვიხილოთ კლასიკური ამოცანა, სეგმენტის მინიმალური მნიშვნელობების პოვნა <math>q </math> შეკითხვისთვის <math>(Range Minimum Queries - (RMQ))</math>.
 
 
481

რედაქტირება