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

არ არის რედაქტირების რეზიუმე
[შეუმოწმებელი ვერსია][შეუმოწმებელი ვერსია]
No edit summary
 
განახლების ფუნქცია
 
<source lang="cpp">
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]);
}
</source>
 
 
ინფორმაციის მოძიების ფუნქცია, ამ შემთხვევაში მინიმალური მნიშვნელობის პოვნა
 
<source lang="cpp">
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));
}
</source>
481

რედაქტირება