1622. Fancy Sequence

Problem Description

You need to implement a class called Fancy that maintains a sequence of integers and supports four operations:

Fancy(): Creates a new empty sequence.
append(val): Adds an integer val to the end of the sequence.
addAll(inc): Adds an integer inc to every existing element in the sequence. This operation only affects elements that were already in the sequence before this call.
multAll(m): Multiplies every existing element in the sequence by an integer m. This operation only affects elements that were already in the sequence before this call.
getIndex(idx): Returns the value at position idx (using 0-based indexing) in the current sequence, modulo 10^9 + 7. If idx is greater than or equal to the length of the sequence, return -1.

The key challenge is efficiently handling the addAll and multAll operations. A naive approach of iterating through all elements for each operation would be too slow for large sequences. The solution uses a Segment Tree with lazy propagation to efficiently apply range updates (addition and multiplication) to the entire sequence.

The Segment Tree maintains lazy propagation tags for both addition and multiplication operations. When applying operations:

For addition: the new value becomes (old_value + inc)
For multiplication: the new value becomes (old_value * m) and any pending additions also get multiplied

Each element is stored at a position in the segment tree (1-indexed internally), and operations are applied to ranges. The append operation adds a new element at position n+1, while addAll and multAll apply their operations to the range [1, n] where n is the current sequence length.

All arithmetic operations are performed modulo 10^9 + 7 to prevent integer overflow.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The first instinct might be to simply store all values in an array and update them directly when addAll or multAll is called. However, this becomes inefficient when we have many elements and frequent update operations - each addAll or multAll would require O(n) time to update all elements.

The key insight is recognizing that addAll and multAll are range update operations that affect all existing elements uniformly. Instead of updating each element immediately, we can defer these operations and apply them lazily when needed.

Think of it like this: if we have a sequence [a, b, c] and we perform addAll(5) followed by multAll(2), instead of immediately computing [2*(a+5), 2*(b+5), 2*(c+5)], we can store the operations themselves and apply them only when we need to retrieve a specific value.

This naturally leads us to consider data structures that excel at range updates with lazy propagation. A Segment Tree is perfect for this because:

Range Updates: We can efficiently mark an entire range (in our case, all existing elements) with pending operations in O(log n) time.
Lazy Propagation: We don't need to immediately apply operations to every element. Instead, we store "lazy" tags at nodes representing the pending operations. These get pushed down the tree only when necessary.
Operation Composition: When multiple operations stack up (like add followed by multiply), we need to compose them correctly. The formula becomes: new_value = old_value * mul + add. The multiplication affects both the original value and any previous additions.
Modular Arithmetic: Since we need results modulo 10^9 + 7, we can apply the modulo operation at each step without affecting correctness.

The segment tree approach transforms our O(n) update operations into O(log n) operations, making the solution efficient even for large sequences with many operations.

Learn more about Segment Tree and Math patterns.

Solution Approach

The solution implements a Segment Tree with lazy propagation to efficiently handle range updates. Let's walk through the key components:

Data Structures

Node Class: Each node in the segment tree contains:

l, r: The range [l, r] this node represents
mid: The midpoint for splitting into child nodes
v: The sum of all values in this range
add: Lazy tag for pending addition operations
mul: Lazy tag for pending multiplication operations (initialized to 1)

SegmentTree Class: Manages the tree operations with a root node covering range [1, 100001].

Core Operations

1. Lazy Propagation (pushdown)

When we need to access child nodes, we first push down any pending operations:

new_value = old_value * mul + (range_size * add)
new_add = old_add * mul + add
new_mul = old_mul * mul

This ensures operations are applied in the correct order: previous operations get scaled by new multiplications.

2. Range Addition (modifyAdd)

To add inc to all elements in range [l, r]:

If current node is completely within range: update the node's value and lazy add tag
Otherwise: push down lazy tags, recursively update children, then update current node's value

3. Range Multiplication (modifyMul)

To multiply all elements in range [l, r] by m:

If current node is completely within range: multiply the node's value, add tag, and mul tag by m
Otherwise: push down lazy tags, recursively update children, then update current node's value

4. Point Query (query)

To get value at a specific position:

Navigate down the tree, pushing down lazy tags along the path
Return the value when we reach the target range

Fancy Class Implementation

The Fancy class wraps the segment tree:

append(val):

Increment counter n
Add val at position n using modifyAdd(n, n, val)

addAll(inc):

Apply addition to range [1, n] using modifyAdd(1, n, inc)

multAll(m):

Apply multiplication to range [1, n] using modifyMul(1, n, m)

getIndex(idx):

Return -1 if idx >= n
Otherwise query position idx + 1 (converting 0-indexed to 1-indexed)

Time Complexity

append: O(log n) - single point update
addAll: O(log n) - range update with lazy propagation
multAll: O(log n) - range update with lazy propagation
getIndex: O(log n) - point query

The segment tree approach ensures all operations remain efficient even with a large number of elements, as we avoid the O(n) cost of updating every element directly.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to see how the segment tree with lazy propagation handles the operations:

Initial State: Empty sequence, segment tree initialized with all zeros.

Step 1: append(2)

Increment n from 0 to 1
Call modifyAdd(1, 1, 2) to add value 2 at position 1
The tree node representing position 1 gets value 2
Sequence: [2]

Step 2: append(3)

Increment n from 1 to 2
Call modifyAdd(2, 2, 3) to add value 3 at position 2
The tree node representing position 2 gets value 3
Sequence: [2, 3]

Step 3: append(7)

Increment n from 2 to 3
Call modifyAdd(3, 3, 7) to add value 7 at position 3
Sequence: [2, 3, 7]

Step 4: multAll(2)

Call modifyMul(1, 3, 2) to multiply all elements in range [1, 3] by 2
Instead of updating each element individually, we update the lazy mul tag at the root node covering [1, 3]
The lazy tag says "multiply everything in this range by 2"
Actual values aren't computed yet - they're still logically [2, 3, 7] with a pending ×2 operation
Logical sequence: [4, 6, 14]

Step 5: addAll(5)

Call modifyAdd(1, 3, 5) to add 5 to all elements in range [1, 3]
The root node now has both multiplication (×2) and addition (+5) lazy tags
These compose as: new_value = old_value * 2 + 5
Logical sequence: [9, 11, 19]

Step 6: getIndex(0)

Convert 0-indexed to 1-indexed: query position 1
As we traverse down to position 1, lazy tags get pushed down:
- The pending operations (×2, then +5) are applied
- Position 1: 2 * 2 + 5 = 9
Return 9

Step 7: append(10)

Increment n from 3 to 4
Call modifyAdd(4, 4, 10) to add value 10 at position 4
This new element is NOT affected by previous multAll or addAll operations
Sequence: [9, 11, 19, 10]

Step 8: multAll(3)

Call modifyMul(1, 4, 3) to multiply all current elements by 3
For positions 1-3: Previous operations (×2, +5) now become (×6, +15) after multiplication by 3
Position 4: Gets ×3 operation
Logical sequence: [27, 33, 57, 30]

Step 9: getIndex(2)

Query position 3 (converting from 0-indexed)
Original value at position 3 was 7
Apply composed operations: 7 * 6 + 15 = 57
Return 57

This example demonstrates the key benefits:

Lazy Updates: Operations are stored as tags rather than immediately applied
Operation Composition: Multiple operations stack correctly (multiply affects both values and previous additions)
Selective Application: New elements added after operations aren't affected by previous operations
Efficient Queries: Values are computed on-demand by applying accumulated operations

Solution Implementation

1MOD = int(1e9 + 7)
2
3
4class SegmentTreeNode:
5    """
6    Node for the segment tree that represents a range [left, right].
7    Supports lazy propagation for addition and multiplication operations.
8    """
9    def __init__(self, left: int, right: int):
10        self.left_child = None
11        self.right_child = None
12        self.left_bound = left  # Left boundary of the range
13        self.right_bound = right  # Right boundary of the range
14        self.mid_point = (left + right) >> 1  # Midpoint for splitting
15        self.sum_value = 0  # Sum of all elements in this range
16        self.lazy_add = 0  # Lazy propagation value for addition
17        self.lazy_multiply = 1  # Lazy propagation value for multiplication
18
19
20class SegmentTree:
21    """
22    Segment tree with lazy propagation supporting range addition and multiplication.
23    """
24    def __init__(self):
25        # Initialize root node covering range [1, 100001]
26        self.root = SegmentTreeNode(1, int(1e5 + 1))
27
28    def modifyAdd(self, left: int, right: int, increment: int, node: SegmentTreeNode = None) -> None:
29        """
30        Add 'increment' to all elements in range [left, right].
31      
32        Args:
33            left: Left boundary of the range (inclusive)
34            right: Right boundary of the range (inclusive)
35            increment: Value to add to each element
36            node: Current node in the recursion (defaults to root)
37        """
38        if left > right:
39            return
40          
41        if node is None:
42            node = self.root
43          
44        # If current node's range is completely within [left, right]
45        if node.left_bound >= left and node.right_bound <= right:
46            # Update the sum for this range
47            range_size = node.right_bound - node.left_bound + 1
48            node.sum_value = (node.sum_value + range_size * increment) % MOD
49            # Mark for lazy propagation
50            node.lazy_add += increment
51            return
52          
53        # Push down lazy values before processing children
54        self._push_down(node)
55      
56        # Recursively update left and right children if they overlap with [left, right]
57        if left <= node.mid_point:
58            self.modifyAdd(left, right, increment, node.left_child)
59        if right > node.mid_point:
60            self.modifyAdd(left, right, increment, node.right_child)
61          
62        # Update current node's value based on children
63        self._push_up(node)
64
65    def modifyMul(self, left: int, right: int, multiplier: int, node: SegmentTreeNode = None) -> None:
66        """
67        Multiply all elements in range [left, right] by 'multiplier'.
68      
69        Args:
70            left: Left boundary of the range (inclusive)
71            right: Right boundary of the range (inclusive)
72            multiplier: Value to multiply each element by
73            node: Current node in the recursion (defaults to root)
74        """
75        if left > right:
76            return
77          
78        if node is None:
79            node = self.root
80          
81        # If current node's range is completely within [left, right]
82        if node.left_bound >= left and node.right_bound <= right:
83            # Apply multiplication to sum and lazy values
84            node.sum_value = (node.sum_value * multiplier) % MOD
85            node.lazy_add = (node.lazy_add * multiplier) % MOD
86            node.lazy_multiply = (node.lazy_multiply * multiplier) % MOD
87            return
88          
89        # Push down lazy values before processing children
90        self._push_down(node)
91      
92        # Recursively update left and right children if they overlap with [left, right]
93        if left <= node.mid_point:
94            self.modifyMul(left, right, multiplier, node.left_child)
95        if right > node.mid_point:
96            self.modifyMul(left, right, multiplier, node.right_child)
97          
98        # Update current node's value based on children
99        self._push_up(node)
100
101    def query(self, left: int, right: int, node: SegmentTreeNode = None) -> int:
102        """
103        Query the sum of elements in range [left, right].
104      
105        Args:
106            left: Left boundary of the range (inclusive)
107            right: Right boundary of the range (inclusive)
108            node: Current node in the recursion (defaults to root)
109          
110        Returns:
111            Sum of elements in the specified range
112        """
113        if left > right:
114            return 0
115          
116        if node is None:
117            node = self.root
118          
119        # If current node's range is completely within [left, right]
120        if node.left_bound >= left and node.right_bound <= right:
121            return node.sum_value
122          
123        # Push down lazy values before querying children
124        self._push_down(node)
125      
126        result = 0
127        # Query left and right children if they overlap with [left, right]
128        if left <= node.mid_point:
129            result = (result + self.query(left, right, node.left_child)) % MOD
130        if right > node.mid_point:
131            result = (result + self.query(left, right, node.right_child)) % MOD
132          
133        return result
134
135    def _push_up(self, node: SegmentTreeNode) -> None:
136        """
137        Update parent node's value based on its children's values.
138      
139        Args:
140            node: Node to update
141        """
142        node.sum_value = (node.left_child.sum_value + node.right_child.sum_value) % MOD
143
144    def _push_down(self, node: SegmentTreeNode) -> None:
145        """
146        Push lazy propagation values down to children nodes.
147        Creates children if they don't exist.
148      
149        Args:
150            node: Node whose lazy values need to be pushed down
151        """
152        # Create children nodes if they don't exist
153        if node.left_child is None:
154            node.left_child = SegmentTreeNode(node.left_bound, node.mid_point)
155        if node.right_child is None:
156            node.right_child = SegmentTreeNode(node.mid_point + 1, node.right_bound)
157          
158        left_child = node.left_child
159        right_child = node.right_child
160      
161        # Apply lazy operations if any exist
162        if node.lazy_add != 0 or node.lazy_multiply != 1:
163            # Apply multiplication first, then addition (order matters!)
164            # Formula: new_value = old_value * multiply + range_size * add
165          
166            # Update left child
167            left_range_size = left_child.right_bound - left_child.left_bound + 1
168            left_child.sum_value = (left_child.sum_value * node.lazy_multiply + 
169                                   left_range_size * node.lazy_add) % MOD
170            left_child.lazy_add = (left_child.lazy_add * node.lazy_multiply + node.lazy_add) % MOD
171            left_child.lazy_multiply = (left_child.lazy_multiply * node.lazy_multiply) % MOD
172          
173            # Update right child
174            right_range_size = right_child.right_bound - right_child.left_bound + 1
175            right_child.sum_value = (right_child.sum_value * node.lazy_multiply + 
176                                    right_range_size * node.lazy_add) % MOD
177            right_child.lazy_add = (right_child.lazy_add * node.lazy_multiply + node.lazy_add) % MOD
178            right_child.lazy_multiply = (right_child.lazy_multiply * node.lazy_multiply) % MOD
179          
180            # Clear parent's lazy values
181            node.lazy_add = 0
182            node.lazy_multiply = 1
183
184
185class Fancy:
186    """
187    A data structure that supports:
188    - Appending integers to the end
189    - Adding a value to all existing elements
190    - Multiplying all existing elements by a value
191    - Getting the value at a specific index
192    """
193    def __init__(self):
194        self.size = 0  # Current number of elements
195        self.tree = SegmentTree()
196
197    def append(self, val: int) -> None:
198        """
199        Append 'val' to the end of the sequence.
200      
201        Args:
202            val: Value to append
203        """
204        self.size += 1
205        # Add the value at position self.size (1-indexed)
206        self.tree.modifyAdd(self.size, self.size, val)
207
208    def addAll(self, inc: int) -> None:
209        """
210        Add 'inc' to all existing elements in the sequence.
211      
212        Args:
213            inc: Value to add to all elements
214        """
215        self.tree.modifyAdd(1, self.size, inc)
216
217    def multAll(self, m: int) -> None:
218        """
219        Multiply all existing elements in the sequence by 'm'.
220      
221        Args:
222            m: Multiplier for all elements
223        """
224        self.tree.modifyMul(1, self.size, m)
225
226    def getIndex(self, idx: int) -> int:
227        """
228        Get the value at index 'idx' (0-indexed).
229      
230        Args:
231            idx: Index to query (0-indexed)
232          
233        Returns:
234            Value at the given index, or -1 if index is out of bounds
235        """
236        if idx >= self.size:
237            return -1
238        # Convert to 1-indexed for the segment tree
239        return self.tree.query(idx + 1, idx + 1)
240
241
242# Your Fancy object will be instantiated and called as such:
243# obj = Fancy()
244# obj.append(val)
245# obj.addAll(inc)
246# obj.multAll(m)
247# param_4 = obj.getIndex(idx)
248

1/**
2 * Node class for Segment Tree
3 * Represents a node in the segment tree with lazy propagation
4 */
5class Node {
6    Node left;              // Left child node
7    Node right;             // Right child node
8    int l;                  // Left boundary of the segment
9    int r;                  // Right boundary of the segment
10    int mid;                // Midpoint of the segment
11    long value;             // Sum value stored in this node
12    long lazyAdd;           // Lazy addition value to be propagated
13    long lazyMultiply = 1;  // Lazy multiplication value to be propagated
14
15    /**
16     * Constructor for Node
17     * @param l left boundary
18     * @param r right boundary
19     */
20    public Node(int l, int r) {
21        this.l = l;
22        this.r = r;
23        this.mid = (l + r) >> 1;  // Bit shift for efficient division by 2
24    }
25}
26
27/**
28 * Segment Tree implementation with lazy propagation
29 * Supports range addition and multiplication operations
30 */
31class SegmentTree {
32    private Node root = new Node(1, (int) 1e5 + 1);  // Root node covering range [1, 100001]
33    private static final int MOD = (int) 1e9 + 7;    // Modulo value for overflow prevention
34
35    public SegmentTree() {
36    }
37
38    /**
39     * Public method to add a value to a range
40     * @param l left boundary of range
41     * @param r right boundary of range
42     * @param inc increment value
43     */
44    public void modifyAdd(int l, int r, int inc) {
45        modifyAdd(l, r, inc, root);
46    }
47
48    /**
49     * Private recursive method to add a value to a range
50     * @param l left boundary of range
51     * @param r right boundary of range
52     * @param inc increment value
53     * @param node current node being processed
54     */
55    private void modifyAdd(int l, int r, int inc, Node node) {
56        // Base case: invalid range
57        if (l > r) {
58            return;
59        }
60      
61        // Current segment is completely within the update range
62        if (node.l >= l && node.r <= r) {
63            // Update node value and lazy propagation value
64            node.value = (node.value + (long)(node.r - node.l + 1) * inc) % MOD;
65            node.lazyAdd = (node.lazyAdd + inc) % MOD;
66            return;
67        }
68      
69        // Push down lazy values before recursing
70        pushdown(node);
71      
72        // Recurse to left child if needed
73        if (l <= node.mid) {
74            modifyAdd(l, r, inc, node.left);
75        }
76      
77        // Recurse to right child if needed
78        if (r > node.mid) {
79            modifyAdd(l, r, inc, node.right);
80        }
81      
82        // Update current node value based on children
83        pushup(node);
84    }
85
86    /**
87     * Public method to multiply a range by a value
88     * @param l left boundary of range
89     * @param r right boundary of range
90     * @param m multiplication factor
91     */
92    public void modifyMul(int l, int r, int m) {
93        modifyMul(l, r, m, root);
94    }
95
96    /**
97     * Private recursive method to multiply a range by a value
98     * @param l left boundary of range
99     * @param r right boundary of range
100     * @param m multiplication factor
101     * @param node current node being processed
102     */
103    private void modifyMul(int l, int r, int m, Node node) {
104        // Base case: invalid range
105        if (l > r) {
106            return;
107        }
108      
109        // Current segment is completely within the update range
110        if (node.l >= l && node.r <= r) {
111            // Update node value and lazy propagation values
112            node.value = (node.value * m) % MOD;
113            node.lazyAdd = (node.lazyAdd * m) % MOD;
114            node.lazyMultiply = (node.lazyMultiply * m) % MOD;
115            return;
116        }
117      
118        // Push down lazy values before recursing
119        pushdown(node);
120      
121        // Recurse to left child if needed
122        if (l <= node.mid) {
123            modifyMul(l, r, m, node.left);
124        }
125      
126        // Recurse to right child if needed
127        if (r > node.mid) {
128            modifyMul(l, r, m, node.right);
129        }
130      
131        // Update current node value based on children
132        pushup(node);
133    }
134
135    /**
136     * Public method to query sum of a range
137     * @param l left boundary of range
138     * @param r right boundary of range
139     * @return sum of values in the range
140     */
141    public int query(int l, int r) {
142        return query(l, r, root);
143    }
144
145    /**
146     * Private recursive method to query sum of a range
147     * @param l left boundary of range
148     * @param r right boundary of range
149     * @param node current node being processed
150     * @return sum of values in the range
151     */
152    private int query(int l, int r, Node node) {
153        // Base case: invalid range
154        if (l > r) {
155            return 0;
156        }
157      
158        // Current segment is completely within the query range
159        if (node.l >= l && node.r <= r) {
160            return (int) node.value;
161        }
162      
163        // Push down lazy values before recursing
164        pushdown(node);
165      
166        int result = 0;
167      
168        // Query left child if needed
169        if (l <= node.mid) {
170            result = (result + query(l, r, node.left)) % MOD;
171        }
172      
173        // Query right child if needed
174        if (r > node.mid) {
175            result = (result + query(l, r, node.right)) % MOD;
176        }
177      
178        return result;
179    }
180
181    /**
182     * Update parent node value based on children values
183     * @param node parent node to update
184     */
185    private void pushup(Node node) {
186        node.value = (node.left.value + node.right.value) % MOD;
187    }
188
189    /**
190     * Push down lazy propagation values to children
191     * @param node parent node with lazy values
192     */
193    private void pushdown(Node node) {
194        // Create children nodes if they don't exist
195        if (node.left == null) {
196            node.left = new Node(node.l, node.mid);
197        }
198        if (node.right == null) {
199            node.right = new Node(node.mid + 1, node.r);
200        }
201      
202        // Apply lazy propagation if there are pending operations
203        if (node.lazyAdd != 0 || node.lazyMultiply != 1) {
204            Node left = node.left;
205            Node right = node.right;
206          
207            // Apply multiplication first, then addition to left child
208            left.value = (left.value * node.lazyMultiply + 
209                         (long)(left.r - left.l + 1) * node.lazyAdd) % MOD;
210            left.lazyAdd = (left.lazyAdd * node.lazyMultiply + node.lazyAdd) % MOD;
211            left.lazyMultiply = (left.lazyMultiply * node.lazyMultiply) % MOD;
212          
213            // Apply multiplication first, then addition to right child
214            right.value = (right.value * node.lazyMultiply + 
215                          (long)(right.r - right.l + 1) * node.lazyAdd) % MOD;
216            right.lazyAdd = (right.lazyAdd * node.lazyMultiply + node.lazyAdd) % MOD;
217            right.lazyMultiply = (right.lazyMultiply * node.lazyMultiply) % MOD;
218          
219            // Reset lazy values after propagation
220            node.lazyAdd = 0;
221            node.lazyMultiply = 1;
222        }
223    }
224}
225
226/**
227 * Fancy class that maintains a sequence of integers
228 * Supports append, add to all, multiply all, and get operations
229 */
230class Fancy {
231    private int sequenceLength;           // Current length of the sequence
232    private SegmentTree segmentTree = new SegmentTree();  // Segment tree to manage operations
233
234    public Fancy() {
235    }
236
237    /**
238     * Append a value to the end of the sequence
239     * @param val value to append
240     */
241    public void append(int val) {
242        ++sequenceLength;
243        // Add value at position sequenceLength (1-indexed)
244        segmentTree.modifyAdd(sequenceLength, sequenceLength, val);
245    }
246
247    /**
248     * Add increment to all existing elements in the sequence
249     * @param inc increment value
250     */
251    public void addAll(int inc) {
252        segmentTree.modifyAdd(1, sequenceLength, inc);
253    }
254
255    /**
256     * Multiply all existing elements in the sequence by m
257     * @param m multiplication factor
258     */
259    public void multAll(int m) {
260        segmentTree.modifyMul(1, sequenceLength, m);
261    }
262
263    /**
264     * Get the value at the given index
265     * @param idx 0-indexed position
266     * @return value at index, or -1 if index is out of bounds
267     */
268    public int getIndex(int idx) {
269        // Check if index is valid
270        if (idx >= sequenceLength) {
271            return -1;
272        }
273        // Query at position idx+1 (convert to 1-indexed)
274        return segmentTree.query(idx + 1, idx + 1);
275    }
276}
277
278/**
279 * Your Fancy object will be instantiated and called as such:
280 * Fancy obj = new Fancy();
281 * obj.append(val);
282 * obj.addAll(inc);
283 * obj.multAll(m);
284 * int param_4 = obj.getIndex(idx);
285 */
286

1const int MOD = 1e9 + 7;
2
3/**
4 * Node class for segment tree
5 * Supports lazy propagation with addition and multiplication operations
6 */
7class Node {
8public:
9    Node* left;      // Left child node
10    Node* right;     // Right child node
11    int l;           // Left boundary of range
12    int r;           // Right boundary of range
13    int mid;         // Middle point of range
14    long long v;     // Sum value of this range
15    long long add;   // Lazy addition tag
16    long long mul;   // Lazy multiplication tag
17
18    Node(int l, int r) {
19        this->l = l;
20        this->r = r;
21        this->mid = (l + r) >> 1;
22        this->left = nullptr;
23        this->right = nullptr;
24        v = 0;
25        add = 0;
26        mul = 1;  // Initial multiplication factor is 1
27    }
28};
29
30/**
31 * Segment Tree with lazy propagation
32 * Supports range addition, range multiplication, and range sum query
33 */
34class SegmentTree {
35private:
36    Node* root;
37
38public:
39    SegmentTree() {
40        // Initialize tree with range [1, 100001]
41        root = new Node(1, 1e5 + 1);
42    }
43
44    // Public interface for range addition
45    void modifyAdd(int l, int r, int increment) {
46        modifyAdd(l, r, increment, root);
47    }
48
49    // Recursive implementation of range addition
50    void modifyAdd(int l, int r, int increment, Node* node) {
51        if (l > r) return;
52      
53        // If current node's range is completely within [l, r]
54        if (node->l >= l && node->r <= r) {
55            // Update node value and lazy tag
56            node->v = (node->v + (long long)(node->r - node->l + 1) * increment) % MOD;
57            node->add = (node->add + increment) % MOD;
58            return;
59        }
60      
61        // Push down lazy tags before recursing
62        pushdown(node);
63      
64        // Recurse on children if they overlap with [l, r]
65        if (l <= node->mid) {
66            modifyAdd(l, r, increment, node->left);
67        }
68        if (r > node->mid) {
69            modifyAdd(l, r, increment, node->right);
70        }
71      
72        // Update current node's value from children
73        pushup(node);
74    }
75
76    // Public interface for range multiplication
77    void modifyMul(int l, int r, int multiplier) {
78        modifyMul(l, r, multiplier, root);
79    }
80
81    // Recursive implementation of range multiplication
82    void modifyMul(int l, int r, int multiplier, Node* node) {
83        if (l > r) return;
84      
85        // If current node's range is completely within [l, r]
86        if (node->l >= l && node->r <= r) {
87            // Update node value and lazy tags
88            node->v = (node->v * multiplier) % MOD;
89            node->add = (node->add * multiplier) % MOD;
90            node->mul = (node->mul * multiplier) % MOD;
91            return;
92        }
93      
94        // Push down lazy tags before recursing
95        pushdown(node);
96      
97        // Recurse on children if they overlap with [l, r]
98        if (l <= node->mid) {
99            modifyMul(l, r, multiplier, node->left);
100        }
101        if (r > node->mid) {
102            modifyMul(l, r, multiplier, node->right);
103        }
104      
105        // Update current node's value from children
106        pushup(node);
107    }
108
109    // Public interface for range sum query
110    int query(int l, int r) {
111        return query(l, r, root);
112    }
113
114    // Recursive implementation of range sum query
115    int query(int l, int r, Node* node) {
116        if (l > r) return 0;
117      
118        // If current node's range is completely within [l, r]
119        if (node->l >= l && node->r <= r) {
120            return node->v;
121        }
122      
123        // Push down lazy tags before querying children
124        pushdown(node);
125      
126        int result = 0;
127        // Query left child if it overlaps with [l, r]
128        if (l <= node->mid) {
129            result = (result + query(l, r, node->left)) % MOD;
130        }
131        // Query right child if it overlaps with [l, r]
132        if (r > node->mid) {
133            result = (result + query(l, r, node->right)) % MOD;
134        }
135      
136        return result;
137    }
138
139    // Update parent node's value from its children
140    void pushup(Node* node) {
141        node->v = (node->left->v + node->right->v) % MOD;
142    }
143
144    // Push down lazy tags to children nodes
145    void pushdown(Node* node) {
146        // Create children nodes if they don't exist (dynamic segment tree)
147        if (!node->left) {
148            node->left = new Node(node->l, node->mid);
149        }
150        if (!node->right) {
151            node->right = new Node(node->mid + 1, node->r);
152        }
153      
154        // If there are pending lazy operations
155        if (node->add != 0 || node->mul != 1) {
156            long long addTag = node->add;
157            long long mulTag = node->mul;
158            Node* leftChild = node->left;
159            Node* rightChild = node->right;
160          
161            // Apply multiplication first, then addition: new_val = old_val * mul + add
162            // Update left child
163            leftChild->v = (leftChild->v * mulTag + (leftChild->r - leftChild->l + 1) * addTag) % MOD;
164            leftChild->add = (leftChild->add * mulTag + addTag) % MOD;
165            leftChild->mul = (leftChild->mul * mulTag) % MOD;
166          
167            // Update right child
168            rightChild->v = (rightChild->v * mulTag + (rightChild->r - rightChild->l + 1) * addTag) % MOD;
169            rightChild->add = (rightChild->add * mulTag + addTag) % MOD;
170            rightChild->mul = (rightChild->mul * mulTag) % MOD;
171          
172            // Clear parent's lazy tags
173            node->add = 0;
174            node->mul = 1;
175        }
176    }
177};
178
179/**
180 * Fancy class that maintains a sequence with operations:
181 * - append: add element to the end
182 * - addAll: add value to all elements
183 * - multAll: multiply all elements by a value
184 * - getIndex: get element at specific index
185 */
186class Fancy {
187private:
188    int n;                  // Current number of elements
189    SegmentTree* tree;      // Segment tree to maintain the sequence
190
191public:
192    Fancy() {
193        n = 0;
194        tree = new SegmentTree();
195    }
196
197    // Append a new value to the end of the sequence
198    void append(int val) {
199        ++n;
200        // Add value at position n (1-indexed in segment tree)
201        tree->modifyAdd(n, n, val);
202    }
203
204    // Add increment to all existing elements
205    void addAll(int inc) {
206        tree->modifyAdd(1, n, inc);
207    }
208
209    // Multiply all existing elements by m
210    void multAll(int m) {
211        tree->modifyMul(1, n, m);
212    }
213
214    // Get the value at index idx (0-indexed)
215    int getIndex(int idx) {
216        // Check if index is valid
217        if (idx >= n) {
218            return -1;
219        }
220        // Query position idx+1 (convert to 1-indexed)
221        return tree->query(idx + 1, idx + 1);
222    }
223};
224
225/**
226 * Your Fancy object will be instantiated and called as such:
227 * Fancy* obj = new Fancy();
228 * obj->append(val);
229 * obj->addAll(inc);
230 * obj->multAll(m);
231 * int param_4 = obj->getIndex(idx);
232 */
233

1const MOD = 1e9 + 7;
2
3/**
4 * Node class for segment tree
5 * Supports lazy propagation with addition and multiplication operations
6 */
7class SegmentTreeNode {
8    left: SegmentTreeNode | null;      // Left child node
9    right: SegmentTreeNode | null;     // Right child node
10    rangeLeft: number;                  // Left boundary of range
11    rangeRight: number;                 // Right boundary of range
12    rangeMid: number;                   // Middle point of range
13    sum: number;                        // Sum value of this range
14    lazyAdd: number;                    // Lazy addition tag
15    lazyMul: number;                    // Lazy multiplication tag
16
17    constructor(left: number, right: number) {
18        this.rangeLeft = left;
19        this.rangeRight = right;
20        this.rangeMid = Math.floor((left + right) / 2);
21        this.left = null;
22        this.right = null;
23        this.sum = 0;
24        this.lazyAdd = 0;
25        this.lazyMul = 1;  // Initial multiplication factor is 1
26    }
27}
28
29// Global variables for Fancy functionality
30let elementCount: number = 0;              // Current number of elements
31let segmentTreeRoot: SegmentTreeNode;      // Root of segment tree
32
33/**
34 * Initialize the Fancy sequence manager
35 */
36function initializeFancy(): void {
37    elementCount = 0;
38    // Initialize tree with range [1, 100001]
39    segmentTreeRoot = new SegmentTreeNode(1, 100001);
40}
41
42/**
43 * Update parent node's value from its children
44 */
45function pushUp(node: SegmentTreeNode): void {
46    if (node.left && node.right) {
47        node.sum = (node.left.sum + node.right.sum) % MOD;
48    }
49}
50
51/**
52 * Push down lazy tags to children nodes
53 */
54function pushDown(node: SegmentTreeNode): void {
55    // Create children nodes if they don't exist (dynamic segment tree)
56    if (!node.left) {
57        node.left = new SegmentTreeNode(node.rangeLeft, node.rangeMid);
58    }
59    if (!node.right) {
60        node.right = new SegmentTreeNode(node.rangeMid + 1, node.rangeRight);
61    }
62  
63    // If there are pending lazy operations
64    if (node.lazyAdd !== 0 || node.lazyMul !== 1) {
65        const addTag = node.lazyAdd;
66        const mulTag = node.lazyMul;
67        const leftChild = node.left;
68        const rightChild = node.right;
69      
70        // Apply multiplication first, then addition: new_val = old_val * mul + add
71        // Update left child
72        const leftRangeSize = leftChild.rangeRight - leftChild.rangeLeft + 1;
73        leftChild.sum = (leftChild.sum * mulTag + leftRangeSize * addTag) % MOD;
74        leftChild.lazyAdd = (leftChild.lazyAdd * mulTag + addTag) % MOD;
75        leftChild.lazyMul = (leftChild.lazyMul * mulTag) % MOD;
76      
77        // Update right child
78        const rightRangeSize = rightChild.rangeRight - rightChild.rangeLeft + 1;
79        rightChild.sum = (rightChild.sum * mulTag + rightRangeSize * addTag) % MOD;
80        rightChild.lazyAdd = (rightChild.lazyAdd * mulTag + addTag) % MOD;
81        rightChild.lazyMul = (rightChild.lazyMul * mulTag) % MOD;
82      
83        // Clear parent's lazy tags
84        node.lazyAdd = 0;
85        node.lazyMul = 1;
86    }
87}
88
89/**
90 * Recursive implementation of range addition
91 */
92function modifyAddRecursive(left: number, right: number, increment: number, node: SegmentTreeNode): void {
93    if (left > right) return;
94  
95    // If current node's range is completely within [left, right]
96    if (node.rangeLeft >= left && node.rangeRight <= right) {
97        // Update node value and lazy tag
98        const rangeSize = node.rangeRight - node.rangeLeft + 1;
99        node.sum = (node.sum + rangeSize * increment) % MOD;
100        node.lazyAdd = (node.lazyAdd + increment) % MOD;
101        return;
102    }
103  
104    // Push down lazy tags before recursing
105    pushDown(node);
106  
107    // Recurse on children if they overlap with [left, right]
108    if (left <= node.rangeMid && node.left) {
109        modifyAddRecursive(left, right, increment, node.left);
110    }
111    if (right > node.rangeMid && node.right) {
112        modifyAddRecursive(left, right, increment, node.right);
113    }
114  
115    // Update current node's value from children
116    pushUp(node);
117}
118
119/**
120 * Recursive implementation of range multiplication
121 */
122function modifyMulRecursive(left: number, right: number, multiplier: number, node: SegmentTreeNode): void {
123    if (left > right) return;
124  
125    // If current node's range is completely within [left, right]
126    if (node.rangeLeft >= left && node.rangeRight <= right) {
127        // Update node value and lazy tags
128        node.sum = (node.sum * multiplier) % MOD;
129        node.lazyAdd = (node.lazyAdd * multiplier) % MOD;
130        node.lazyMul = (node.lazyMul * multiplier) % MOD;
131        return;
132    }
133  
134    // Push down lazy tags before recursing
135    pushDown(node);
136  
137    // Recurse on children if they overlap with [left, right]
138    if (left <= node.rangeMid && node.left) {
139        modifyMulRecursive(left, right, multiplier, node.left);
140    }
141    if (right > node.rangeMid && node.right) {
142        modifyMulRecursive(left, right, multiplier, node.right);
143    }
144  
145    // Update current node's value from children
146    pushUp(node);
147}
148
149/**
150 * Recursive implementation of range sum query
151 */
152function queryRecursive(left: number, right: number, node: SegmentTreeNode): number {
153    if (left > right) return 0;
154  
155    // If current node's range is completely within [left, right]
156    if (node.rangeLeft >= left && node.rangeRight <= right) {
157        return node.sum;
158    }
159  
160    // Push down lazy tags before querying children
161    pushDown(node);
162  
163    let result = 0;
164    // Query left child if it overlaps with [left, right]
165    if (left <= node.rangeMid && node.left) {
166        result = (result + queryRecursive(left, right, node.left)) % MOD;
167    }
168    // Query right child if it overlaps with [left, right]
169    if (right > node.rangeMid && node.right) {
170        result = (result + queryRecursive(left, right, node.right)) % MOD;
171    }
172  
173    return result;
174}
175
176/**
177 * Append a new value to the end of the sequence
178 */
179function append(val: number): void {
180    elementCount++;
181    // Add value at position elementCount (1-indexed in segment tree)
182    modifyAddRecursive(elementCount, elementCount, val, segmentTreeRoot);
183}
184
185/**
186 * Add increment to all existing elements
187 */
188function addAll(inc: number): void {
189    modifyAddRecursive(1, elementCount, inc, segmentTreeRoot);
190}
191
192/**
193 * Multiply all existing elements by m
194 */
195function multAll(m: number): void {
196    modifyMulRecursive(1, elementCount, m, segmentTreeRoot);
197}
198
199/**
200 * Get the value at index idx (0-indexed)
201 */
202function getIndex(idx: number): number {
203    // Check if index is valid
204    if (idx >= elementCount) {
205        return -1;
206    }
207    // Query position idx+1 (convert to 1-indexed)
208    return queryRecursive(idx + 1, idx + 1, segmentTreeRoot);
209}
210
211// Initialize on module load
212initializeFancy();
213

Time and Space Complexity

Time Complexity:

append(val): O(log n) - The operation calls modifyAdd on a single element, which traverses the segment tree from root to leaf. The tree height is O(log n) where n is the range size (10^5).
addAll(inc): O(log n) - The operation calls modifyAdd on the range [1, n]. Due to lazy propagation, if the entire range matches a node's range, the update is done in O(1) at that node. Otherwise, it traverses down the tree, taking O(log n) time.
multAll(m): O(log n) - Similar to addAll, it calls modifyMul on the range [1, n] with lazy propagation, resulting in O(log n) time complexity.
getIndex(idx): O(log n) - The operation calls query for a single element, which traverses from root to the target leaf node, taking O(log n) time.

Space Complexity:

The segment tree uses dynamic node creation (nodes are created only when needed during pushdown).
In the worst case, after multiple operations, the tree could have up to O(n) nodes where n is the maximum range (10^5).
Each node stores a constant amount of data (l, r, mid, v, add, mul).
The Fancy class itself only stores the tree and a counter n.
Overall space complexity: O(n) where n is up to 10^5.

Note: The lazy propagation technique ensures that updates are deferred and only applied when necessary, keeping the time complexity logarithmic for range updates rather than linear.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Operations in Lazy Propagation

One of the most critical pitfalls in this solution is applying multiplication and addition operations in the wrong order during lazy propagation. When pushing down lazy values, the order matters significantly.

The Problem: Consider a sequence where we have pending operations:

First: multiply by 2
Then: add 3

If we apply these in the wrong order (add first, then multiply), we get:

Wrong: (value + 3) * 2 = value * 2 + 6
Correct: value * 2 + 3

The Solution: Always apply multiplication first, then addition. When combining operations:

# Correct order in _push_down method:
new_value = old_value * lazy_multiply + range_size * lazy_add
new_lazy_add = old_lazy_add * lazy_multiply + lazy_add
new_lazy_mul = old_lazy_mul * lazy_multiply

2. Forgetting to Handle Modulo Operations Consistently

The Problem: Integer overflow can occur during multiplication operations, and forgetting to apply modulo at any step can lead to incorrect results or runtime errors.

The Solution: Apply modulo operation after every arithmetic operation:

# Always use modulo after operations
node.sum_value = (node.sum_value * multiplier) % MOD
node.lazy_add = (node.lazy_add * multiplier) % MOD
node.lazy_multiply = (node.lazy_multiply * multiplier) % MOD

3. Not Initializing Lazy Multiplication to 1

The Problem: If lazy multiplication is initialized to 0 instead of 1, all values will become 0 when the lazy tag is applied, destroying all data.

The Solution: Always initialize lazy_multiply = 1 in the node constructor:

def __init__(self, left: int, right: int):
    # ... other initializations
    self.lazy_add = 0  # Addition identity is 0
    self.lazy_multiply = 1  # Multiplication identity is 1, NOT 0!

4. Incorrect Range Size Calculation in Lazy Propagation

The Problem: When applying an addition operation lazily, the contribution to the sum depends on the range size. Forgetting to multiply the lazy addition value by the range size will give incorrect sum values.

The Solution: Always multiply the lazy addition by the range size when updating the sum:

range_size = node.right_bound - node.left_bound + 1
node.sum_value = (node.sum_value + range_size * increment) % MOD

5. Index Conversion Errors (0-indexed vs 1-indexed)

The Problem: The Fancy class uses 0-indexed positions for the user interface, but the segment tree internally uses 1-indexed positions. Mixing these up causes off-by-one errors.

The Solution: Consistently convert indices:

def getIndex(self, idx: int) -> int:
    if idx >= self.size:  # Check using 0-indexed logic
        return -1
    # Convert to 1-indexed for segment tree query
    return self.tree.query(idx + 1, idx + 1)

6. Not Creating Child Nodes Before Accessing Them

The Problem: In a dynamic segment tree, child nodes might not exist yet. Attempting to access them without checking can cause AttributeError.

The Solution: Always create child nodes in the _push_down method before accessing them:

def _push_down(self, node: SegmentTreeNode) -> None:
    if node.left_child is None:
        node.left_child = SegmentTreeNode(node.left_bound, node.mid_point)
    if node.right_child is None:
        node.right_child = SegmentTreeNode(node.mid_point + 1, node.right_bound)

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: