Pytania otagowane jako intervals

1
Struktura danych dla mapy w odstępach czasu
Niech będzie liczbą całkowitą, a oznacza zbiór wszystkich liczb całkowitych. Niech oznacza przedział liczb całkowitych .nnnZZ\mathbb{Z}[a,b][a,b][a,b]{a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} Szukam struktury danych do reprezentowania mapy . Chcę, aby struktura danych obsługiwała następujące operacje:f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} get(i)get(i)\text{get}(i) should return f(i)f(i)f(i). set([a,b],y)set([a,b],y)\text{set}([a,b],y) should update fff so that f(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=⋯=f(b)=yf(a)=f(a+1)=\cdots=f(b)=y, i.e., update fff to a new map …

1
Dowód złożoności czasu dla implementacji problemu segmentu dystansowego w drzewie segmentów
Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(log⁡n)\mathcal{O}(\log n)czas zgodnie z tutorialem tutaj . Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście O (logn )O(log⁡n)\mathcal{O}(\log n). Ten link (i wiele innych) mówi, że możemy udowodnić, że …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.