სეგმენტური ხე
სეგმენტური ხე კომპიუტერულ მეცნიერებაში — ორობითი ხე, რომელიც მასივის სეგმენტების ან ინტერვალების შესანახად გამოიყენება. თითოეული კვანძი წარმოადგენს მასივის გარკვეული სეგმენტის შესახებ ინფორმაციას. ის ძალიან ზოგადი მონაცემთა სტრუქტურაა და უამრავ ამოცანას წარმატებით ხსნის. ყველაზე ცნობილია გარკვეულ სეგმენტზე ჯამის, ან მინიმალური/მაქსიმალური მნიშვნელობის პოვნა. ამ ყველა ოპერაციას სეგმენტური ხე ლოგარითმულ დროში აკეთებს, რაც გაცილებით სწრაფია ვიდრე პირდაპირი, ბრუტ-ფორს მიდგომა. სეგმენტური ხისთვის ძირითადად სამ ოპერაციას განიხილავენ: მისი აგება, სეგმენტის შესახებ ინფორმაციის მოძიება და განახლება. როგორც წესი, რადგან სეგმენტური ხე ორობითი ხეა, ის წრფივ მონაცემთა სტრუქტურაში იწერება. სეგმენტური ხე სტატიკურია, რადგან აგების შემდეგ მისი სტრუქტურის შეცვლა არ ხდება, მხოლოდ კვანძების მნიშვნელობების შეცვლა ხდება განახლების ოპერაციის დროს. სეგმენტური ხის აგებას O ( n ) {\displaystyle O(n)} დრო სჭირდება, მაგრამ თუ ყოველი ელემენტისთვის გავუშვებთ განახლების ფუნქციას იმუშავებს O ( n log ⁡ n ) {\displaystyle O(n\log n)} -ში, რადგან თითოეული n {\displaystyle n} ელემენტისთვის საჭიროა განახლების ოპერაციის გამოყენება, რომელიც O ( log ⁡ n ) {\displaystyle O(\log n)} დროში მუშაობს. რაც შეეხება მეხსიერებას, მისი ასიმპტოტიკა O ( n log ⁡ n ) {\displaystyle O(n\log n)} - ია. შევნიშნოთ, რომ სეგმენტური ხის აგების შემდეგ, სეგმენტის შესახებ ინფორმაციის მოძიება და განახლება O ( log ⁡ n ) {\displaystyle O(\log n)} - დროში მუშაობს, სწორედ ეს არის მისი უპირატესობა. აგრეთვე, სეგმენტური ხე შეიძლება 1-ზე მეტ განზომილებიანიც იყოს.