1622. Fancy Sequence

Problem Description

The task is to build a data structure that allows efficient manipulation of an integer sequence. The Fancy class supports adding a new element to the sequence, applying an increment operation to all elements in the sequence, multiplying all elements by a given integer, and retrieving the element at a specific index position modulo 10^9 + 7. It must perform these operations in such a way that getIndex queries return the correct updated value after any number of addAll and multAll operations have been applied, or return -1 if the index is out of bounds.

Intuition

The main challenge in the given problem is that applying addAll and multAll operations naively to every element each time they are called will lead to a time complexity that is not feasible for large sequences and frequent updates.

To efficiently handle this, we need to defer these operations as much as possible so that we don’t actually apply them until necessary (i.e., when an element's value is queried with getIndex).

This can be achieved using a Segment Tree, a data structure that allows efficient updates and queries on ranges of elements in a sequence. However, this is not a standard segment tree implementation. It needs to support not only the addition and multiplication operations but also the propagation of these operations to its child nodes (a process called lazy propagation). This ensures that we don’t perform the operation for every element immediately, but only apply it to segments and update child segments when needed.

The segment tree nodes are augmented with additional information that allows combining these operations efficiently. In this case, each node in the segment tree will contain three pieces of information: the total result of applying all queued operations to the segment (the value), the sum of all addAll increments that need to be applied to the segment (add), and the product of all multAll multiplications that need to be applied (mul).

The tree is built so that leaf nodes correspond to elements of our sequence. When an operation is called, we update the relevant segment(s) in the tree, marking the operation as pending to be applied later (lazy propagation). Upon a getIndex query, as we traverse the tree, all pending operations for that particular segment are applied, ensuring that the returned value is correct.

The provided solution code implements this logic in a SegmentTree class providing the necessary methods for adding, multiplying and querying nodes.

Learn more about Segment Tree and Math patterns.

Solution Approach

The solution approach utilizes a segment tree to handle range updates and queries efficiently. Let's walk through the main components of the implementation:

Segment Tree Structure (`Node` class)

Each node represents a segment of the sequence. It contains:

left and right: Pointers to child nodes.
l and r: The segment's range (inclusive).
mid: The midpoint for dividing the segment for child nodes.
v: The computed value with all operations applied.
add: The accumulated addition to be applied to the segment.
mul: The accumulated multiplication to be applied to the segment.

The root node represents the entire sequence range.

Key Operations of `SegmentTree` class

modifyAdd and modifyMul: These methods apply the add and multiply operations to a specified range. Both operations update the current node's deferred operation fields (add and mul) and values. They rely on recursion to propagate changes to relevant child nodes lazily.
query: This method retrieves the value at a specific index. If any deferred operations are pending on the path from root to the target index, query applies them. It ensures that the final result returned is up to date with all applied operations.
pushup: After child nodes are updated, pushup updates the current node's value (the sum of its children's values, modulo MOD), ensuring the segment tree accurately represents the current sequence values.
pushdown: This method is where the lazy propagation magic happens. When accessing a node's children, pushdown applies all the pending add and mul operations to its child nodes to ensure they have the correct deferred values. This way, the operations are propagated down the tree as necessary without unnecessary computation.

Interactions in `Fancy` class

The Fancy class employs the following methods to interact with the SegmentTree:

append: Simply increments the sequence's count (self.n) and uses modifyAdd to append the new value to the end of the sequence.
addAll: Calls modifyAdd to apply the addition operation across the entire sequence.
multAll: Calls modifyMul to apply the multiplication operation across the entire sequence.
getIndex: Utilize the query method to return the modified value at the index if within bounds, else -1.

Through this implementation, the Fancy class wraps the efficient range update and query functionalities provided by the SegmentTree, allowing it to process a sequence of alterations and fetches with much better performance than a naive approach.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Consider a Fancy object where we perform the following sequence of operations to understand how the solution approach works in practice:

Append 2 to the sequence.
Multiply all elements by 3.
Add 4 to all elements.
Append 6 to the sequence.
Multiply all elements by 2.
Retrieve the value at index 0.
Retrieve the value at index 1.

Here's what happens at each step:

Append 2: The sequence is [2]. The segment tree is updated to have a root node representing this value.
Multiply all elements by 3: Instead of multiplying the single element directly, the root node's mul value is updated to 3. The sequence is conceptually [6], but no computation is done yet.
Add 4 to all elements: Similarly, the root node's add value is updated to 4. The sequence should be [10] now, but again, no operations are applied yet.
Append 6: The sequence now is [10, 6], with 6 to be added at the end of the segment tree structure, increasing the sequence count. The root is split into two children to accommodate this change.
Multiply all elements by 2: The whole tree's mul value is updated to 2, and the add value is appropriately adjusted considering the previous multiply operation. The sequence conceptually becomes [20, 12].
Retrieve the value at index 0: The getIndex query now triggers the lazy propagation. The segment tree updates the value of the node representing index 0 with the mul and add values, computing (2*3) * (2) + (4*2) to return 20.
Retrieve the value at index 1: For index 1, getIndex would compute (6*3) * (2) + (4*2) and return 44.

At every operation that mutates the sequence (addAll, multAll), we update only the values and operations pending on the segment tree without recalculating the entire sequence. The getIndex operation applies all pending operations that are on the path to the requested element. This lazy propagation and segmented representation grant efficiency, ensuring that querying an element's value after numerous addAll and multAll operations are still done quickly.

Solution Implementation

1MOD = int(1e9 + 7)
2
3
4class Node:
5    def __init__(self, start, end):
6        # Initializing the segment tree node
7        self.left = None  # Left child
8        self.right = None  # Right child
9        self.start = start  # Start index of the segment
10        self.end = end  # End index of the segment
11        self.mid = (start + end) >> 1  # Middle index of the segment
12        self.value = 0  # Value of node
13        self.add = 0  # Lazy addition value
14        self.mul = 1  # Lazy multiplication value
15
16
17class SegmentTree:
18    def __init__(self):
19        # Initialize segment tree with root node covering range [1, 1e5 + 1]
20        self.root = Node(1, int(1e5 + 1))
21
22    def modify_add(self, start, end, increment, node=None):
23        if start > end:
24            return
25        if node is None:
26            node = self.root
27        # If the current node's range is completely within the update range
28        if node.start >= start and node.end <= end:
29            node.value = (node.value + (node.end - node.start + 1) * increment) % MOD
30            node.add += increment
31            return
32        self.push_down(node)
33        # Update left child if the update range intersects it
34        if start <= node.mid:
35            self.modify_add(start, end, increment, node.left)
36        # Update right child if the update range intersects it
37        if end > node.mid:
38            self.modify_add(start, end, increment, node.right)
39        self.push_up(node)
40
41    def modify_mul(self, start, end, multiplier, node=None):
42        if start > end:
43            return
44        if node is None:
45            node = self.root
46        # If the current node's range is completely within the update range
47        if node.start >= start and node.end <= end:
48            node.value = (node.value * multiplier) % MOD
49            node.add = (node.add * multiplier) % MOD
50            node.mul = (node.mul * multiplier) % MOD
51            return
52        self.push_down(node)
53        # Update left child if the update range intersects it
54        if start <= node.mid:
55            self.modify_mul(start, end, multiplier, node.left)
56        # Update right child if the update range intersects it
57        if end > node.mid:
58            self.modify_mul(start, end, multiplier, node.right)
59        self.push_up(node)
60
61    def query(self, start, end, node=None):
62        if start > end:
63            return 0
64        if node is None:
65            node = self.root
66        # If the current node's range is completely within the query range
67        if node.start >= start and node.end <= end:
68            return node.value
69        self.push_down(node)
70        result = 0
71        # Query left child if the query range intersects it
72        if start <= node.mid:
73            result = (result + self.query(start, end, node.left)) % MOD
74        # Query right child if the query range intersects it
75        if end > node.mid:
76            result = (result + self.query(start, end, node.right)) % MOD
77        return result
78
79    def push_up(self, node):
80        # Push the updates up to the parent node
81        node.value = (node.left.value + node.right.value) % MOD
82
83    def push_down(self, node):
84        # Lazy propagation: push updates down to children nodes
85        if node.left is None:
86            node.left = Node(node.start, node.mid)
87        if node.right is None:
88            node.right = Node(node.mid + 1, node.end)
89        if node.add != 0 or node.mul != 1:
90            self.apply_updates(node.left, node.mul, node.add)
91            self.apply_updates(node.right, node.mul, node.add)
92            node.add = 0
93            node.mul = 1
94
95    def apply_updates(self, child, mul, add):
96        # Apply multiplication and addition updates to child nodes
97        child.value = (child.value * mul + (child.end - child.start + 1) * add) % MOD
98        child.add = (child.add * mul + add) % MOD
99        child.mul = (child.mul * mul) % MOD
100
101
102class Fancy:
103    def __init__(self):
104        self.size = 0  # Initializing the number of elements added
105        self.tree = SegmentTree()  # New segment tree instance
106
107    def append(self, val: int) -> None:
108        # Appends a new element to the array
109        self.size += 1
110        self.tree.modify_add(self.size, self.size, val)
111
112    def add_all(self, increment: int) -> None:
113        # Adds an increment to all elements of the array
114        self.tree.modify_add(1, self.size, increment)
115
116    def mult_all(self, multiplier: int) -> None:
117        # Multiplies all elements of the array by multiplier
118        self.tree.modify_mul(1, self.size, multiplier)
119
120    def get_index(self, index: int) -> int:
121        # Returns the element at the given index
122        return -1 if index >= self.size else self.tree.query(index + 1, index + 1)
123
124
125# Usage example:
126# fancy = Fancy()
127# fancy.append(val)
128# fancy.add_all(inc)
129# fancy.mult_all(m)
130# result = fancy.get_index(idx)
131

1class Node {
2    Node left;
3    Node right;
4    int start;
5    int end;
6    int mid;
7    long value; // Segment value with lazy propagation of additions and multiplication
8    long addLazy; // Lazy value for range addition
9    long multLazy = 1; // Lazy value for range multiplication, initialized to 1 (neutral for multiplication)
10
11    public Node(int start, int end) {
12        this.start = start;
13        this.end = end;
14        this.mid = (start + end) >> 1; // Midpoint calculation using bitwise shift for efficiency
15    }
16}
17
18class SegmentTree {
19    private Node root = new Node(1, (int) 1e5 + 1); // Initialize the tree with 10^5 elements
20    private static final int MOD = (int) 1e9 + 7; // Large prime for modulo operation
21
22    // Empty constructor for the SegmentTree class
23    public SegmentTree() {
24    }
25
26    // Public method to perform range addition
27    public void modifyAdd(int start, int end, int increment) {
28        modifyAdd(start, end, increment, root);
29    }
30
31    // Helper method to perform range addition
32    private void modifyAdd(int start, int end, int increment, Node node) {
33        if (start > end) {
34            return;
35        }
36        if (node.start >= start && node.end <= end) {
37            node.value = (node.value + (long) (node.end - node.start + 1) * increment) % MOD;
38            node.addLazy = (node.addLazy + increment) % MOD;
39            return;
40        }
41        pushDown(node);
42        if (start <= node.mid) {
43            modifyAdd(start, end, increment, node.left);
44        }
45        if (end > node.mid) {
46            modifyAdd(start, end, increment, node.right);
47        }
48        pushUp(node);
49    }
50
51    // Public method to perform range multiplication
52    public void modifyMul(int start, int end, int multiplier) {
53        modifyMul(start, end, multiplier, root);
54    }
55
56    // Helper method to perform range multiplication
57    private void modifyMul(int start, int end, int multiplier, Node node) {
58        if (start > end) {
59            return;
60        }
61        if (node.start >= start && node.end <= end) {
62            node.value = (node.value * multiplier) % MOD;
63            node.addLazy = (node.addLazy * multiplier) % MOD;
64            node.multLazy = (node.multLazy * multiplier) % MOD;
65            return;
66        }
67        pushDown(node);
68        if (start <= node.mid) {
69            modifyMul(start, end, multiplier, node.left);
70        }
71        if (end > node.mid) {
72            modifyMul(start, end, multiplier, node.right);
73        }
74        pushUp(node);
75    }
76
77    // Public method to query the sum in a range
78    public int query(int start, int end) {
79        return query(start, end, root);
80    }
81
82    // Helper method to query the sum in a range
83    private int query(int start, int end, Node node) {
84        if (start > end) {
85            return 0;
86        }
87        if (node.start >= start && node.end <= end) {
88            return (int) node.value;
89        }
90        pushDown(node);
91        int total = 0;
92        if (start <= node.mid) {
93            total = (total + query(start, end, node.left)) % MOD;
94        }
95        if (end > node.mid) {
96            total = (total + query(start, end, node.right)) % MOD;
97        }
98        return total;
99    }
100
101    // Method to propagate the value from parent to children after lazy updates
102    private void pushUp(Node node) {
103        node.value = (node.left.value + node.right.value) % MOD;
104    }
105
106    // Method to apply lazy updates to the current segment
107    private void pushDown(Node node) {
108        if (node.left == null) {