Thinking of using advanced data structures? You are thinking it too complicated.

For each update operation, do you really need to update all elements between i and j?

Update only the first and end element is sufficient.

The optimal time complexity is O(<b><i>k</i></b> + <b><i>n</i></b>) and uses O(1) extra space.