Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers.  Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$.I am looking for a data structure to represent a map $f:[1,n] \to \mathbb{Z}$.  I want the data structure to support the following operations:$\text{get}(i)$ should return $f(i)$.$\text{set}([a,b],y)$ should update $f$ so that $f(a)=f(a+1)=\cdots=f(b)=y$, i.e., update $f$ to a new map $f'$ such that $f'(i) = y$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.$\text{stab}(i)$ should return the largest interval $[a,b]$ such that $i \in [a,b]$ and $f$ is constant on $[a,b]$ (i.e., $f(a)=f(a+1)=\cdots=f(b)$).$\text{add}([a,b],\delta)$ should update $f$ to a new map $f'$ such that $f'(i) = f(i) + \delta$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.I want each of these operations to be efficient.  I would count $O(1)$ or $O(\lg n)$ time as efficient, but $O(n)$ time is too slow.  It's OK if the running times are amortized running times.  Is there a data structure that simultaneously makes all of these operations efficient?(I've noticed a similar pattern come up in a several programming challenges.  This is a generalization that would suffice for all of those challenge problems.)
Data structure for map on intervals
algorithms;data structures;trees;intervals