Witam. Ostatnio znalazłem takie zadanie: https://szkopul.edu.pl/problemset/problem/-0A1PC3fNc2RK-qvoUQKGGLl/site/?key=statement. Zadanie sprowadza się do tego, żeby umieć odczytać maksymalną wartość z danego przedziału, a następnie przypisać wstawić wartość o jeden większą na tym przedziale (nie dodać, tylko przypisać). Oczywiście zadanie można rozwiązać dzieląc cały przedział na mniejsze podprzedziały o długości ~ sqrt(d) i uzyskać złożoność O(n * sqrt(d)), ale zadanie da się też zrobić używając drzewa przedziałowego (przedział-przedział). Ostatnio miałem przyjemność napisać drzewo typu (+,+), czyli dodajemy wartość na danym przedziale i odczytujemy sumę. Zrobiłem to tak, że w każdym węźle drzewa binarnego trzymam 2 wartości: W i w. Załóżmy, że mam drzewo binarne, które ma liście numerowane od 16 do 31, to w węźle nr. 1 będzie suma na całym przedziale, w 2 suma od 16 do 23, a np. w 5 od 20 do 23. Czyli jeżeli będę chciał znać sumę na przedziale <19, 26> to będę rozważał przedziały bazowe, które obejmują węzły: 19, 5, 12, 26, czyli zsumuję wartości W dla tych wierzchołków. Druga wartość trzymana w węźle - w jest wartością pomocniczą. Jeżeli np. w wierzchołku nr. 5 W=10, w = 3 (10, 4) to jeżeli będę chciał dodać 4 na przedziale <20, 23> to znaczy, że do W i w dodam 4 * 4 (26, 20). Załóżmy, że pytam o jakiś przedział, którego jeden z wierzchołków bazowych ma numer 11. Mam rekurencyjną funkcję do wyszukiwania przedziałów bazowych, czyli zaczynam od 1, następnie idę do 2, 5... Przyjmijmy, że w 5 wartości W i w = (26, 10). Wtedy dodaję synom 5 czyli 10 i 11 po połowie (czyli po 5) do W i w. 10 na razie nie ruszam, bo idę do 11. Tam dodaję jakąś wartość do W i w i spycham w w ten sam sposób dalej do synów (22, 23). Wiem, że lekkiego pióra nie mam, więc załączam kod i obrazek pomocniczy.
https://pastebin.com/D1FkSVvT
tree
img upload

W kodzie oprócz samego drzewa mam także napisaną funkcję losującą przykładowe zestawy danych oraz bruta, którym sprawdzałem poprawność (testowane na dużych przedziałach, dużych zestawach danych, jest ok).
W podobny sposób chciałem zrobić drzewo typu (max, max), W byłoby największą wartością W w poddrzewie, natomiast w byłoby wartością pomocniczą, której jednak nie dzieliłbym na pół, tylko obu synom przypisywałbym taką samą wartość. Niestety takie podejście chyba nie jest poprawne, albo coś zbugowałem. Jak powinno działać takie drzewo? A może gdzie mum buga? Przepraszam, za nieścisłości i brak fachowego języka, którego osobiście nienawidzę (najlepsze jest tłumaczenie na obrazkach i przykładach).

#include <iostream>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using namespace::std;
int W[3000], w[3000], test[3000], wynik;
void show() {
    int p = 1;
    for(int i = 1; i <= 32; i++) {
        cout << "("<< i << ":" << W[i] << "," << w[i] <<")";
        if(i==p) {
            cout << endl;
            p = 2*p+1;
        }
    }
}
void insert(int x, int a, int b, int p, int k, int v) {
	bool baza = false;
	if(a==p && b==k) {
		//cout << v << endl;
		W[v] = x; w[v] = x;
		baza = true;
	}
	if(w[v]!=0) {
		W[2*v] = w[v]; w[2*v] = w[v];
		W[2*v+1] = w[v]; w[2*v+1] = w[v];
		w[v] = 0;		
	}
	
	if(!baza) {
		int sr = (p+k)/2;
		if(b <= sr) insert(x, a, b, p, sr, 2 * v);
		else if(a > sr) insert(x, a, b, sr+1, k, 2 * v+1);
		else {
			insert(x, a, sr, p, sr, 2 * v);
			insert(x, sr+1, b, sr+1, k, 2 * v + 1);
		}
		W[v] = max(W[2*v], W[2*v+1]);		
	}
}

void query(int a, int b, int p, int k, int v) {
	bool baza = false;
	if(a==p && b==k) {
		//cout << v << endl;
		wynik = max(wynik, W[v]);
		baza = true;
	}
	if(w[v]!=0) {
		W[2*v] = W[v]; w[2*v] = W[v];
		W[2*v+1] = W[v]; w[2*v+1] = W[v];
		w[v] = 0;		
	}
	
	if(!baza) {
		int sr = (p+k)/2;
		if(b <= sr) query(a, b, p, sr, 2 * v);
		else if(a > sr) query(a, b, sr+1, k, 2 * v+1);
		else {
			query(a, sr, p, sr, 2 * v);
			query(sr+1, b, sr+1, k, 2 * v + 1);
		}
		W[v] = max(W[2*v], W[2*v+1]);		
	}
}
void wstaw(int a, int b, int _x) {
    for(int i = a; i <= b; i++) test[i] = _x;
}
int czytaj(int a, int b) {
    int wyn = 0;
    for(int i = a; i <= b; i++) wyn = max(test[i], wyn);
    return wyn;
}
void losuj() {
    srand(time(NULL));
    int ile = 5000;
    for(int i = 0; i < ile; i++) {
        int t = rand()%2, A = rand()%1023+1024, B = rand()%(2047-A)+A;
        if(t==0) {
            insert(i+1, A, B, 1024, 2047, 1);
            wstaw(A, B, i+1);
        }
        else {
			query(A, B, 1024, 2047, 1);
			cout << (wynik==czytaj(A, B)) << endl;
            wynik = 0;
        }  
    }
}
int main() {
	losuj();
}