First of all instead of storing the numbers just store the modulos. That is each A[i] change it to A[i] % 3. This way you just have to deal with 3 numbers 0, 1 and 2.

In the tree node store an array cnt[0..2] this stores the count of all the numbers with such mods for that Range.

In the lazy node store the pending updates % 3. ( See yourself why )

When updating lazily Apply the pending updates.

• If there is no pending update do nothing,

• If there is 1 pending update change. (like cnt[1] will become cnt[0], cnt[2] = cnt[1] and cnt[0] = cnt[2] )

• If there are 2 pending updates swap(cnt[2], cnt[0] ) and cnt[1] won't be affected.

Finally answer for a range is just summing cnt[0]'s for appropriate ranges ( like standard sum query)