A Very Detailed Explanation of the MULTQ3 Problem
(For Beginners and First-Time Learners)
1 The Problem in Very Simple Words
You are given an array of numbers.
• Initially, all numbers are 0
• You will be given many queries
Each query is one of two types:
1.1 Type 0 Query (Update)
Increase every number from index A to B by 1.
1.2 Type 1 Query (Question)
How many numbers from index A to B are divisible by 3?
2 Why a Simple Solution Does NOT Work
The simplest idea is:
• Actually increase every element for update queries
• Check every element for query queries
This would take:
O(N ) time per query
But:
• N can be very large
• Number of queries Q can also be very large
Total time:
O(N × Q)
This is too slow.
We need something much faster.
1
3 Key Insight #1: We Only Care About Divisibility by 3
To check if a number is divisible by 3, we only care about:
number mod 3
Possible remainders are:
0, 1, 2
3.1 Important Observation
If we add 1 to a number:
0→1
1→2
2→0
So adding 1 just cycles the remainder.
4 Rephrasing the Problem
Instead of storing the actual numbers, we will store:
• How many numbers have remainder 0
• How many numbers have remainder 1
• How many numbers have remainder 2
5 Segment Tree: The Big Idea
A segment tree is a data structure that:
• Splits the array into segments
• Stores information about each segment
• Allows fast range updates and queries
5.1 What Each Node Stores
Each node stores a triple:
(zero, one, two)
Meaning:
zero count of numbers divisible by 3
one count of numbers giving remainder 1
two count of numbers giving remainder 2
This corresponds to the trio class in code.
2
6 Initial State of the Tree
Initially:
a[i] = 0 ⇒ a[i] mod 3 = 0
So each leaf node stores:
(1, 0, 0)
7 Building the Segment Tree
• Leaves represent single elements
• Internal nodes combine children
7.1 Combining Two Children
If left child has:
(z1 , o1 , t1 )
and right child has:
(z2 , o2 , t2 )
Then parent stores:
(z1 + z2 , o1 + o2 , t1 + t2 )
8 What Happens When We Increment a Range?
Incrementing means:
(zero, one, two) → (two, zero, one)
This is a rotation.
8.1 Why Rotation Works
Because:
• Numbers that were divisible by 3 become remainder 1
• Remainder 1 becomes remainder 2
• Remainder 2 becomes divisible by 3
9 The Lazy Propagation Idea
Imagine updating a very large range.
Updating every leaf individually is slow.
Instead:
• Update the current node
• Mark that children should be updated later
This marking is done using a lazy array.
3
10 What Does Lazy Mean?
“I know this segment has been incremented, but I will fix the children later when
needed.”
Lazy value stores:
number of pending increments
Since modulo is 3:
lazy = lazy mod 3
11 Applying Lazy Updates
Before using a node:
• Apply all pending rotations
• Push lazy value to children
• Reset lazy value
12 Query Operation Explained
For a query 1 A B:
• If segment is completely outside: return 0
• If segment is fully inside: return zero
• Otherwise:
– Push lazy updates
– Query left and right children
– Add results
13 Update Operation Explained
For update 0 A B:
• If outside range: do nothing
• If fully inside:
– Rotate counts
– Increase lazy value of children
• Otherwise:
– Push lazy
– Recurse to children
– Rebuild current node
4
14 Visual Example
(2,1,0)
(1,1,0) (1,0,0)
Each node stores remainder counts.
15 Why This Is Efficient
• Each query touches O(log N ) nodes
• Rotations are constant time
• Lazy propagation avoids unnecessary work
16 Final Complexity
Time: O((N + Q) log N ) Space: O(N )
17 Mental Model to Remember
We do not store numbers. We store how many numbers belong to each remainder class.
Updates rotate these classes. Lazy propagation delays work safely.
18 Why This Solution Is Elegant
• Converts arithmetic into rotations
• Uses only small constant states
• Works for very large input sizes
19 Conclusion
This problem looks hard at first, but becomes simple once we:
• Think in modulo
• Use segment trees
• Apply lazy propagation correctly