Recall the red$-$black tree structure we discuss in class. It manages n entries, of

which each is a pair of key and value, $($key$,$ value$)$ and supports, in O$($log n$)$ time, the

operations search$($x$),$ insert$($x$)$ and delete$($x$),$ where x is a key for some entry.

Describe how to augment a red$-$black tree to support, in O$($log n$)$ time, the operations

increase$($x$,$ y$,$ q$)$ and decrease$($x$,$ y$,$ q$).$ That is to have additional fields $($or attributes$)$ used in the structure. In increase$($x$,$ y$,$ q$),$ the value $($w$.$value$)$ of every entry

w in the tree with key, x $<=$ w$.$key $<=$ y$,$ is increased by q $($the decrease operation does

the corresponding decrease$).$ One cannot explicitly update the entries as this may take

O$($n$)$ time. Describe how all operations can be executed in O$($log n$)$ time.