Salve a tutti, sto provando a risolvere muraglia da qualche giorno e sono riuscito (almeno penso) a creare correttamente il segment tree e a sviluppare la funzione update però non riesco a creare la funzione chiedi.
Ho seguito il consiglio di usare la funzione get_first su questo sito ma non ottengo i valori che cerco e in generale non so interpretarli perché non mi è molto chiaro cosa fa questa funzione.
Ecco il codice fin’ora:
#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
void build(int u, int sx, int dx, vector<int> data){
if(dx - sx == 1){
if(sx < data.size())
nodes[u] = data[sx];
}
else{
int m = (sx+dx)/2;
build(2*u, sx, m, data);
build(2*u+1, m, dx, data);
nodes[u]= max(nodes[2*u], nodes[2*u+1]);
}
}
void inizializza(int N, vector<int> data){
size = 1;
while(size < N)
size *= 2;
nodes.assign(2*size, -1); // totale nodi=2*N-1
build(1, 0, size, data);
}
void cambia(int x, int h){
int p = size + x; //size è il primo del vector
nodes[p] = h;
while(p>1){
p/=2; //risalgo
nodes[p] = max(nodes[2*p], nodes[2*p+1]);
}
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
if(sx > b or dx < a) return -1;
if(a <= sx and dx <= b){
if(nodes[pos] <= x) return -1;
while(sx != dx){
int m = sx + (dx-sx)/2;
if(nodes[2*pos] > x){
pos = 2*pos;
dx = m;
}
else{
pos = 2*pos+1;
sx = m+1;
}
}
return sx;
}
int m = sx + (dx-sx)/2;
int rs = succ(2*pos, sx, m, a, b, x);
if(rs != -1) return rs;
return succ(2*pos+1, m+1, dx, a, b, x);
}
//pair<int, int>
int chiedi(int x){
int pos = succ(1, x+1, 2*size, x+1, 2*size, x);
return pos;
}
int main(){
int N = 14;
vector<int> data = {7, 4, 78, 2, 6, 4, 1, 9, 10, 7, 100, 56, 8, 1};
inizializza(N, data);
for(int i=1; i<nodes.size(); i++){ //stampo il ST
if(i==2 or i==4 or i==8 or i==16) cout<<"\n";
cout<<nodes[i]<<"\t";
}
cambia(7, 3); //test update
cout<<"\n\n";
cout<<chiedi(1)<<endl; //test chiedi
return 0;
}