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

არ არის რედაქტირების რეზიუმე
No edit summary
No edit summary
სეგმენტური ხე სტატიკურია, რადგან აგების შემდეგ მისი სტრუქტურის შეცვლა არ ხდება, მხოლოდ კვანძების მნიშვნელობების შეცვლა ხდება განახლების ოპერაციის დროს.
 
სეგმენტური ხის აგებას <math>O(n\log n)</math> დრო სჭირდება, მაგრამ თუ ყოველი ელემენტისთვის გავუშვებთ განახლების ფუნქციას იმუშავებს <math>O(n\log n)</math>-ში, რადგან თითოეული <math>n</math>ელემენტისთვის საჭიროა განახლების ოპერაციის გამოყენება, რომელიც <math>O(\log n)</math> დროში მუშაობს. რაც შეეხება მეხსიერებას, მისი ასიმპტოტიკაც აგრეთვეასიმპტოტიკა <math>O(n\log n)</math> - ია. შევნიშნოთ, რომ სეგმენტური ხის აგების შემდეგ, სეგმენტის შესახებ ინფორმაციის მოძიება და განახლება <math>O(\log n)</math> - დროში მუშაობს, სწორედ ეს არის მისი უპირატესობა.
 
აგრეთვე, სეგმენტური ხე შეიძლება 1-ზე მეტ განზომილებიანიც იყოს.
481

რედაქტირება