You are not logged in. Please login at to post your questions!


ENTRY - Editorial



Author: Rupesh Maity
Tester: Asim Krishna Prasad
Editorialist: Rupesh Maity




Segment Tree, Lazy Propagation


Given an array whose elements are set to 0 initially, apply two operations:
Update: given (L, R), update arr[i] = (arr[i] + 1) % 10, for all L <= i <= R.
Sum: given (L, R), find the sum of all the elements of the array in the range L to R (both inclusive).


Maintain a segment tree where each node contains the count of the number of occurances of each number from 0 to 9 and maintain a lazy component for each of these nodes. An update would require the circular shifting of the count of occurances of these numbers and updating the parent nodes accordingly.


You need to first learn about Lazy Propagation to understand the most standard way to solve this problem. Since we only have integers ranging from 0 to 9, it is possible to maintain the count of occurances of each of these integers in every node of the segment tree. An update to any node requires us to circular shift the occurance count towards the right. That is, if you're supposed to update for a node representing the range (l, r), such that(L <= l <= r <= R), where (L, R) is the update range in the question, the count of occurances of 0 is shited to 1, 1 to 2 and so on till 9 to 0. This is a circular shift. We're doing this because all the 0s in this range are converted to 1s and so on for every element. Remember, we are also maintaining a lazy component to be updated later for all the children. The count of all the parent nodes are updated accordingly in each step. Now to find the sum of this range, we can simply use this count of occurances. Remember to take care of those lazy updates ;)

This editorial was written assuming that you know about lazy propagation. If you don't, I recommend you solve a few basic lazy propagation related questions and come back to this question later.

Author's Solution:

Author's solution can be found here.

This question is marked "community wiki".

asked 06 Oct '16, 18:27

deathsurgeon's gravatar image

accept rate: 0%

edited 06 Oct '16, 20:21


main () { int a [5],i,sum=0,ar [5]; printf ("enter the elements of an array\n"); for (i=0;i <5;i++) scanf ("%d",&a [i]); for (i=0;i <5;i++) { ar [i]=a [i]; sum=sum+ar [i]; printf ("%d",ar [i]); } printf ("%d",sum); }


answered 06 Oct '16, 20:13

nidhibt1212's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 06 Oct '16, 18:27

question was seen: 763 times

last updated: 06 Oct '16, 20:21