Witam, męczy mnie od kilku godzin problem znalezienia największej wartości w przedziale [x, y] w drzewie przedziałowym. Jeśli umie to ktoś oraz ma chwilę czasu to prosiłbym o wytłumaczenie w postaci pseudokodu lub kodu. Z góry dziękuję oraz załączam wyniki mojej pracy (udało mi się zbudować drzewo przedziałowe oraz napisać funkcję podmieniającą wartość w tablicy o indeksie x na wartość y).
*Dodam, iż moje drzewo przedziałowe liczy maksimum, a nie sumę wartości tablicy.
**Załączam także zadanie, bo bez niego raczej nie zrozumiecie mojego kodu: link
#include <iostream>
#include <algorithm>
using namespace std;
int q, n, m, x, y;
int a[1000007];
int log2(int x) {
int n = 1, i = 0;
while (n < x) {
n <<= 1;
i ++;
}
return i;
}
bool czyPot2(int w) {
if (w == 1) return 1;
if (w % 2 == 0) return czyPot2(w / 2);
return 0;
}
void buduj() {
for (int i = q + 1; i <= q + n; i ++)
cin >> a[i];
if (czyPot2(n) != 1) {
int tmp = 1 << log2(n);
tmp -= n;
for (int i = q + n + 1; i <= q + n + tmp; i ++)
a[i] = -1e6;
}
for (int i = q; i >= 1; i --)
a[i] = max(a[i * 2], a[i * 2 + 1]);
}
int fnMax(int x, int y) {
//TUTAJ NIE WIEM CO NAPISAC
return 1;
}
void update(int x, int y) {
a[x + q] = y;
for (int i = (x + q) / 2; i >= 1; i >>= 2)
a[i] = max(a[i * 2], a[i * 2 + 1]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string s;
cin >> n >> m;
q = (1 << log2(n)) - 1;
buduj();
/*for (int i = 1; i <= m; i ++) {
cin >> s >> x >> y;
if (s == "MAX") cout << fnMax(x, y) << '\n';
else update(x, y);
}*/
}