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 …