სეგმენტური ხე

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
Jump to navigation Jump to search

კომპიუტერულ მეცნიერებაში, სეგმენტური ხე არის ორობითი ხე, რომელიც მასივის სეგმენტების ან ინტერვალების შესანახად გამოიყენება. თითოეული კვანძი წარმოადგენს მასივის გარკვეული სეგმენტის შესახებ ინფორმაციას. ის ძალიან ზოგადი მონაცემთა სტრუქტურაა და უამრავ ამოცანას წარმატებით ხსნის. ყველაზე ცნობილია გარკვეულ სეგმენტზე ჯამის, ან მინიმალური/მაქსიმალური მნიშვნელობის პოვნა. ამ ყველა ოპერაციას სეგმენტური ხე ლოგარითმულ დროში აკეთებს, რაც გაცილებით სწრაფია ვიდრე პირდაპირი, ბრუტ-ფორს მიდგომა. სეგმენტური ხისთვის ძირითადად ორ ოპერაციას განიხილავენ: სეგმენტის შესახებ ინფორმაციის მოძიება და ინფორმაციის განახლება. ასევე აგებაც განიხილება, მაგრამ ეს შეგვიძლია ცარიელი ხის განახლებად ჩავთვალოთ. როგორც წესი, რადგან სეგმენტური ხე ორობითი ხეა, ის წრფივ მონაცემთა სტრუქტურაში იწერება.

სეგმენტური ხე სტატიკურია, რადგან აგების შემდეგ მისი სტრუქტურის შეცვლა არ ხდება, მხოლოდ კვანძების მნიშვნელობების შეცვლა ხდება განახლების ოპერაციის დროს.

სეგმენტური ხის აგებას დრო სჭირდება, რადგან თითოეული ელემენტისთვის საჭიროა განახლების ოპერაციის გამოყენება, რომელიც დროში მუშაობს. რაც შეეხება მეხსიერებას, მისი ასიმპტოტიკაც აგრეთვე - ია. შევნიშნოთ, რომ სეგმენტური ხის აგების შემდეგ, სეგმენტის შესახებ ინფორმაციის მოძიება და განახლება - დროში მუშაობს, სწორედ ეს არის მისი უპირატესობა.

აგრეთვე, სეგმენტური ხე შეიძლება 1-ზე მეტ განზომილებიანიც იყოს.

სტრუქტურა და იმპლემენტაცია[რედაქტირება | წყაროს რედაქტირება]

სეგმენტური ხის ფესვში მოცემულია მთლიანი მასივის შესახებ ინფორმაცია, ანუ ( - მასივის ზომა), მის მარცხენა შვილში , მარჯვენაში და ასე შემდეგ. შევნიშნოთ, რომ სეგმენტი ორ ნაწილად იყოფა. თუ სეგმენტის ზომა კენტია, არ აქვს მნიშვნელობა მარჯვენაში იქნება მარცხენაზე ერთით მეტი ზომის მქონე სეგმენტი - თუ პირიქით. სეგმენტური ხის ფოთლები, მარცხნიდან მარჯვნივ წარმოადგენენ მასივის ელემენტებს, რადგან ბოლოში მაქსიმალურად დაყოფილი, ანუ ერთ ელემენტიანი სეგმენტებია.

სეგმენტურის ხის სტრუქტურის გრაფიკული მაგალითი

განვიხილოთ კლასიკური ამოცანა, სეგმენტის მინიმალური მნიშვნელობების პოვნა შეკითხვისთვის (Range Minimum Queries - (RMQ)).


განახლების ფუნქცია C++ - ზე

ფუნქციის არგუმენტები :

node - მიმდინარე კვანძი, თავიდან ვიწყებთ პირველიდან.

start და end - სეგმენტის ბოლოები

index - ინდექსი, რომლის მნიშვნელობაც ხდება val

void update(int node, int start, int end, int index, int val) {
        // შემოწმება: კვანძი ფოთოლი არის თუ არა
        if (start == end) {
                tree[node] = val;
                return;
        }

        // თუ არა, ვაგრძელებთ განახლებას
        int mid = (start + end) / 2;
        if (index <= mid)
                update(2 * node, start, mid, index, val);
        else
                update(2 * node + 1, mid + 1, end, index, val);


        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}


ინფორმაციის მოძიების ფუნქცია, ამ შემთხვევაში მინიმალური მნიშვნელობის პოვნა C++ - ზე

int rmq(int node, int start, int end, int l, int r) {
        // თუ მოცემული კვანძი სეგმენტის ფარგლებს ცდება
        if (l > end || r < start)
                return INT_MAX; // ჩავთვალოთ, უსასრულობას ვაბრუნებთ

        // თუ მოცემული კვანძი მთლიანად არის მოქცეული სეგმენტში
        if (start >= l && end <= r)
                return tree[node];

        // თუ არა, ვაგრძელებთ ძებნას
        int m = (start + end) / 2;
        return min(rmq(2 * node, start, m, l, r),
              rmq(2 * node + 1, m + 1, end, l, r));
}

რესურსები ინტერნეტში[რედაქტირება | წყაროს რედაქტირება]

ლიტერატურა[რედაქტირება | წყაროს რედაქტირება]

  • HackerEarth - Segment Trees Tutorials & Notes