**Consider the following problem:**↵
↵
Given an initial array of $n$ integers and, you´re asked to perform $q$ queries of the form:↵
↵
$I$ $x$ $V$ : Add $V$ to the $x$-th position on the vector. If it is not empty (equals 0) then add it between the positions $x$ and $x + 1$.↵
↵
$S$ $x$ $y$ : Calculate the sum of all elements from index $x$ to $y$, inclusively.↵
↵
My teacher has advised us to use *RMQ* or an *Offline Segment Tree* for this one, but i would like to know if there´s a way of adapting the Fenwick Tree to support this sort of *shift* that may need to be done on the vector efficiently.
↵
Given an initial array of $n$ integers
↵
$I$ $x$ $V$ : Add $V$ to the $x$-th position on the vector. If it is not empty (equals 0) then add it between the positions $x$ and $x + 1$.↵
↵
$S$ $x$ $y$ : Calculate the sum of all elements from index $x$ to $y$, inclusively.↵
↵
My teacher has advised us to use *RMQ* or an *Offline Segment Tree* for this one, but i would like to know if there´s a way of adapting the Fenwick Tree to support this sort of *shift* that may need to be done on the vector efficiently.
