Element rotation in segment tree

Question

Given an array A with N numbers(all positive and contain less than or equal to 4 digits), 2 types of queries are to be supported. There are total M queries.

1. Update a range given by indices L,R(both inclusive) by K.
2. Return the maximum element in a range given by L,R(both inclusive).

Updating a number K times implies rotating the number K times.

For e.g. 1234 rotates into 2341

905 rotates into 059 and 059 rotates into 590.

Note : 059 and 59 are different numbers. 59 rotates into 95.

Given array elements don't have leading zeroes.

Constraints:

0 <= Ai < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

I thought of a segment tree in which the tree nodes store the number of rotations of the range they contain. I implemented this with lazy propogation but with the lazy propogation too my query implementation takes O(N) time in the worst case, which is leading to TIME LIMIT EXCEEDED.

Can anyone propose a faster approach?

Am I missing some property of the array or structure?

Answer 1

Your idea of storing the number of rotation is correct.
Here is how to make it work fatser(O(log N)per query).
1)Node structure definition:

class Node:
    int shift = 0 //number of rotations
    int max[12] //maximum value for shift = 0..11
    Node left_child //the left child of this node
    Node right_child //the right child of this node

2)Propagation:

void propagate(Node node):
    node.left_child.shift += node.shift
    node.left_child.shift %= 12
    node.right_child.shift += node.shift
    node.right_child.shift %= 12
    node.shift = 0
    for i = 0..11:
        node.max[i] = max(get_max(node.left_child, i), 
                          get_max(node.right_child, i))

int get_max(Node node, int shift):
     return node.max[(shift + node.shift) % 12]

3)Update and get operation can be implemented like in a conventional segment tree.

Why does it work fast? Because propagate is not recursive. It is called only for those nodes which are visited during the tree traversal when answering a query. And there are only O(log N) such nodes per query(due to the properties of a segment tree).

Why is constant 12 used? Because lcm(1, 2, 3, 4) = 12.(1, 2, 3, 4 are possible numbers of digits of each array element).