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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

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.

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

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

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) {
109            node.left = new Node(node.start, node.mid);
110        }
111        if (node.right == null) {
112            node.right = new Node(node.mid + 1, node.end);
113        }
114        if (node.addLazy != 0 || node.multLazy != 1) {
115            Node left = node.left, right = node.right;
116            left.value = (left.value * node.multLazy + (long) (left.end - left.start + 1) * node.addLazy) % MOD;
117            right.value = (right.value * node.multLazy + (long) (right.end - right.start + 1) * node.addLazy) % MOD;
118            left.addLazy = (left.addLazy * node.multLazy + node.addLazy) % MOD;
119            right.addLazy = (right.addLazy * node.multLazy + node.addLazy) % MOD;
120            left.multLazy = (left.multLazy * node.multLazy) % MOD;
121            right.multLazy = (right.multLazy * node.multLazy) % MOD;
122            node.addLazy = 0;
123            node.multLazy = 1;
124        }
125    }
126}
127
128class Fancy {
129    private int size; // Tracks the number of elements appended
130    private SegmentTree tree = new SegmentTree();
131
132    // Empty constructor for the Fancy class
133    public Fancy() {
134    }
135
136    // Append a new value to the Fancy object
137    public void append(int val) {
138        size++;
139        tree.modifyAdd(size, size, val);
140    }
141
142    // Add the increment to all elements
143    public void addAll(int increment) {
144        tree.modifyAdd(1, size, increment);
145    }
146
147    // Multiply all elements by the given multiplier
148    public void multAll(int multiplier) {
149        tree.modifyMul(1, size, multiplier);
150    }
151
152    // Get the element at the given index
153    public int getIndex(int index) {
154        return index >= size ? -1 : tree.query(index + 1, index + 1);
155    }
156}
157
158/**
159 * Your Fancy object will be instantiated and called as such:
160 * Fancy obj = new Fancy();
161 * obj.append(val);
162 * obj.addAll(inc);
163 * obj.multAll(m);
164 * int param_4 = obj.getIndex(idx);
165 */
166

1const int MOD = 1e9 + 7;
2
3// Definition of the Segment Tree Node
4class SegmentTreeNode {
5public:
6    SegmentTreeNode* left;
7    SegmentTreeNode* right;
8    int start;
9    int end;
10    int mid;
11    long long value;
12    long long lazyAdd;
13    long long lazyMul;
14
15    // Node constructor
16    SegmentTreeNode(int start, int end) {
17        this->start = start;
18        this->end = end;
19        this->mid = (start + end) >> 1; // Midpoint for dividing the range
20        this->left = this->right = nullptr;
21        value = lazyAdd = 0;
22        lazyMul = 1;
23    }
24};
25
26// Definition of the Segment Tree
27class SegmentTree {
28private:
29    SegmentTreeNode* root;
30
31public:
32    // SegmentTree constructor
33    SegmentTree() {
34        root = new SegmentTreeNode(1, 1e5 + 1);
35    }
36
37    // Public method to perform range addition
38    void modifyAdd(int start, int end, int increment) {
39        modifyAdd(start, end, increment, root);
40    }
41
42    // Helper method to perform range addition
43    void modifyAdd(int start, int end, int increment, SegmentTreeNode* node) {
44        if (start > end) return;
45        if (node->start >= start && node->end <= end) {
46            node->value = (node->value + (node->end - node->start + 1) * (long long)increment) % MOD;
47            node->lazyAdd = (node->lazyAdd + increment) % MOD;
48            return;
49        }
50        pushDown(node);
51        if (start <= node->mid) modifyAdd(start, end, increment, node->left);
52        if (end > node->mid) modifyAdd(start, end, increment, node->right);
53        pushUp(node);
54    }
55
56    // Public method to perform range multiplication
57    void modifyMul(int start, int end, int multiplier) {
58        modifyMul(start, end, multiplier, root);
59    }
60
61    // Helper method to perform range multiplication
62    void modifyMul(int start, int end, int multiplier, SegmentTreeNode* node) {
63        if (start > end) return;
64        if (node->start >= start && node->end <= end) {
65            node->value = (node->value * (long long)multiplier) % MOD;
66            node->lazyAdd = (node->lazyAdd * (long long)multiplier) % MOD;
67            node->lazyMul = (node->lazyMul * (long long)multiplier) % MOD;
68            return;
69        }
70        pushDown(node);
71        if (start <= node->mid) modifyMul(start, end, multiplier, node->left);
72        if (end > node->mid) modifyMul(start, end, multiplier, node->right);
73        pushUp(node);
74    }
75
76    // Public method to query the sum in a given range
77    int query(int start, int end) {
78        return query(start, end, root);
79    }
80
81    // Helper method to query the sum in a given range
82    int query(int start, int end, SegmentTreeNode* node) {
83        if (start > end) return 0;
84        if (node->start >= start && node->end <= end) return node->value;
85        pushDown(node);
86        long long sum = 0;
87        if (start <= node->mid) sum = (sum + query(start, end, node->left)) % MOD;
88        if (end > node->mid) sum = (sum + query(start, end, node->right)) % MOD;
89        return (int)sum;
90    }
91
92    // Method to update the parent node based on the values of its children
93    void pushUp(SegmentTreeNode* node) {
94        node->value = (node->left->value + node->right->value) % MOD;
95    }
96
97    // Method to propagate the lazy values to the children nodes
98    void pushDown(SegmentTreeNode* node) {
99        // Create children if they don't exist
100        if (!node->left) node->left = new SegmentTreeNode(node->start, node->mid);
101        if (!node->right) node->right = new SegmentTreeNode(node->mid + 1, node->end);
102
103        // Propagate and combine lazy values: multiplication first, then addition
104        if (node->lazyAdd || node->lazyMul != 1) {
105            // Apply lazy values to children nodes
106            applyLazy(node->left, node->lazyMul, node->lazyAdd);
107            applyLazy(node->right, node->lazyMul, node->lazyAdd);
108
109            // Reset lazy values in the parent node after propagation
110            node->lazyAdd = 0;
111            node->lazyMul = 1;
112        }
113    }
114
115    // Helper method to apply lazy values to a node
116    void applyLazy(SegmentTreeNode* node, long long mul, long long add) {
117        node->value = (node->value * mul + (node->end - node->start + 1) * add) % MOD;
118        node->lazyAdd = (node->lazyAdd * mul + add) % MOD;
119        node->lazyMul = (node->lazyMul * mul) % MOD;
120    }
121};
122
123// Fancy class with operations such as append, addAll, multAll, and getIndex
124class Fancy {
125public:
126    int size; // Size of the sequence
127    SegmentTree* tree;
128
129    // Fancy constructor
130    Fancy() {
131        size = 0;
132        tree = new SegmentTree();
133    }
134
135    // Append a value to the sequence
136    void append(int val) {
137        ++size;
138        tree->modifyAdd(size, size, val);
139    }
140
141    // Add an increment to all elements of the sequence
142    void addAll(int inc) {
143        tree->modifyAdd(1, size, inc);
144    }
145
146    // Multiply all elements of the sequence by a multiplier
147    void multAll(int m) {
148        tree->modifyMul(1, size, m);
149    }
150
151    // Get the element at a specific index of the sequence
152    int getIndex(int idx) {
153        if (idx >= size) return -1; // If the index is out of bounds, return -1
154        return tree->query(idx + 1, idx + 1); // Note: segment tree uses 1-based indexing
155    }
156};
157
158// Example of how the Fancy class objects would be used (not part of the code to be executed)
159/*
160Fancy* obj = new Fancy();
161obj->append(val);
162obj->addAll(inc);
163obj->multAll(m);
164int result = obj->getIndex(idx);
165*/
166

1const MOD: number = 1e9 + 7;
2
3// Definition of the Segment Tree Node
4class SegmentTreeNode {
5    public left: SegmentTreeNode | null;
6    public right: SegmentTreeNode | null;
7    public start: number;
8    public end: number;
9    public mid: number;
10    public value: number;
11    public lazyAdd: number;
12    public lazyMul: number;
13
14    constructor(start: number, end: number) {
15        this.start = start;
16        this.end = end;
17        this.mid = start + end >> 1; // Midpoint for dividing the range
18        this.left = this.right = null;
19        this.value = 0;
20        this.lazyAdd = 0;
21        this.lazyMul = 1;
22    }
23}
24
25let segmentTreeRoot: SegmentTreeNode = new SegmentTreeNode(1, 1e5 + 1);
26
27function modifyAdd(start: number, end: number, increment: number, node: SegmentTreeNode = segmentTreeRoot): void {
28    if (start > end) return;
29    if (node.start >= start && node.end <= end) {
30        node.value = (node.value + (node.end - node.start + 1) * increment) % MOD;
31        node.lazyAdd = (node.lazyAdd + increment) % MOD;
32        return;
33    }
34    pushDown(node);
35    if (start <= node.mid) modifyAdd(start, end, increment, node.left!);
36    if (end > node.mid) modifyAdd(start, end, increment, node.right!);
37    pushUp(node);
38}
39
40function modifyMul(start: number, end: number, multiplier: number, node: SegmentTreeNode = segmentTreeRoot): void {
41    if (start > end) return;
42    if (node.start >= start && node.end <= end) {
43        node.value = node.value * multiplier % MOD;
44        node.lazyAdd = node.lazyAdd * multiplier % MOD;
45        node.lazyMul = node.lazyMul * multiplier % MOD;
46        return;
47    }
48    pushDown(node);
49    if (start <= node.mid) modifyMul(start, end, multiplier, node.left!);
50    if (end > node.mid) modifyMul(start, end, multiplier, node.right!);
51    pushUp(node);
52}
53
54function query(start: number, end: number, node: SegmentTreeNode = segmentTreeRoot): number {
55    if (start > end) return 0;
56    if (node.start >= start && node.end <= end) return node.value;
57    pushDown(node);
58    let sum: number = 0;
59    if (start <= node.mid) sum = (sum + query(start, end, node.left!)) % MOD;
60    if (end > node.mid) sum = (sum + query(start, end, node.right!)) % MOD;
61    return sum;
62}
63
64function pushUp(node: SegmentTreeNode): void {
65    node.value = (node.left!.value + node.right!.value) % MOD;
66}
67
68function pushDown(node: SegmentTreeNode): void {
69    if (!node.left) node.left = new SegmentTreeNode(node.start, node.mid);
70    if (!node.right) node.right = new SegmentTreeNode(node.mid + 1, node.end);
71    if (node.lazyAdd !== 0 || node.lazyMul !== 1) {
72        applyLazy(node.left, node.lazyMul, node.lazyAdd);
73        applyLazy(node.right, node.lazyMul, node.lazyAdd);
74        node.lazyAdd = 0;
75        node.lazyMul = 1;
76    }
77}
78
79function applyLazy(node: SegmentTreeNode, mul: number, add: number): void {
80    node.value = (node.value * mul + (node.end - node.start + 1) * add) % MOD;
81    node.lazyAdd = (node.lazyAdd * mul + add) % MOD;
82    node.lazyMul *= mul;
83    node.lazyMul %= MOD;
84}
85
86// Global variables for the Fancy class functions
87let sequenceSize: number = 0;
88
89function append(val: number): void {
90    sequenceSize++;
91    modifyAdd(sequenceSize, sequenceSize, val);
92}
93
94function addAll(inc: number): void {
95    modifyAdd(1, sequenceSize, inc);
96}
97
98function multAll(m: number): void {
99    modifyMul(1, sequenceSize, m);
100}
101
102function getIndex(idx: number): number {
103    if (idx >= sequenceSize) return -1;
104    return query(idx + 1, idx + 1);
105}
106

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

The provided code implements a segment tree to manage a dynamic array with support for range additions, multiplications, and retrieval of an element by its index.

Time Complexity

SegmentTree Construction: The segment tree is lazily constructed. Each node is only created when needed. Thus, the initial construction is O(1).
modifyAdd (Adding to a Range): It has a complexity of O(log n) where n is the range of the segment tree because the function recursively splits the range [l, r] often in two.
modifyMul (Multiplying to a Range): Similar to modifyAdd, modifyMul affects nodes along the depth of the segment tree, taking O(log n) for each call.
query (Retrieving an Element): The time complexity is O(log n) since it traverses from root to leaf to find the value at a specific index.

Overall, each operation—append, addAll, multAll, and getIndex—performed on the Fancy class is utilizing the above operations, hence each has a O(log n) time complexity.

Space Complexity

Overall Space Complexity: The space complexity is O(n) for storing n elements in the worst case where all nodes in the tree are utilized.
SegmentTree Node Storage: Each SegmentTree node has constant space for attributes, so the space complexity due to a single node is O(1). But since a new node is created for each unique segment during operations, the total space used by all nodes can reach up to O(n).
Lazy Propagation: Since the tree utilizes lazy propagation for adding and multiplying, there's an additional constant space used for each node to store the add and mul values, but it doesn't change the overall O(n) space complexity.

In conclusion, the operations are efficient in terms of time especially for range updates and queries, but can potentially use significant space depending on the number of elements and operations performed.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1622. Fancy Sequence

Problem Description

Intuition

Solution Approach

Segment Tree Structure (Node class)

Key Operations of SegmentTree class

Interactions in Fancy class

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Segment Tree Structure (`Node` class)

Key Operations of `SegmentTree` class

Interactions in `Fancy` class