{x}
blog image

Fancy Sequence

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

  • Fancy() Initializes the object with an empty sequence.
  • void append(val) Appends an integer val to the end of the sequence.
  • void addAll(inc) Increments all existing values in the sequence by an integer inc.
  • void multAll(m) Multiplies all existing values in the sequence by an integer m.
  • int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.

 

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: [2]
fancy.addAll(3);   // fancy sequence: [2+3] -> [5]
fancy.append(7);   // fancy sequence: [5, 7]
fancy.multAll(2);  // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

 

Constraints:

  • 1 <= val, inc, m <= 100
  • 0 <= idx <= 105
  • At most 105 calls total will be made to append, addAll, multAll, and getIndex.

Solution Explanation

This problem requires designing a data structure to handle a dynamic sequence of integers with three main operations: append, addAll, and multAll. A naive approach using a simple array would be inefficient because addAll and multAll would require iterating through the entire array with each call. To optimize, we leverage a Segment Tree.

Segment Tree Approach

A segment tree is a tree data structure used for storing information about intervals or segments. In this case, each node in the tree stores information about a segment of the sequence:

  • v: The sum of the values in the segment (modulo 109 + 7).
  • add: The increment added to all values in the segment.
  • mul: The multiplier applied to all values in the segment.

The tree is built recursively, dividing the sequence into smaller segments until each segment contains only one element. Operations addAll and multAll are propagated down the tree to efficiently update all affected segments. getIndex retrieves the value at a specific index using a query on the tree.

Operations:

  • append(val): Adds a new element to the end of the sequence. This involves updating the leaf node corresponding to the new element and propagating changes up the tree.

  • addAll(inc): Adds inc to every element in the sequence. This is done by updating the add and v values of the root node and propagating these changes down the tree using a process called pushdown. The pushdown operation distributes the add and mul values down to the children nodes.

  • multAll(m): Multiplies every element in the sequence by m. Similar to addAll, this involves updating the mul, add, and v values of the root and propagating using pushdown.

  • getIndex(idx): Retrieves the value at the given index. This involves traversing the tree to find the leaf node at the given index and then applying the accumulated add and mul values from the parent nodes to get the final value.

Time and Space Complexity

  • Time Complexity:

    • append: O(log n), where n is the length of the sequence (due to segment tree updates).
    • addAll: O(log n) (updates root and propagates).
    • multAll: O(log n) (updates root and propagates).
    • getIndex: O(log n) (traverses the tree).

  • Space Complexity: O(n) to store the segment tree.

Code Explanation (Python Example)

The Python code demonstrates the implementation of the Fancy class using a segment tree. Key functions are:

  • Node class: Represents a node in the segment tree, storing the segment's data (v, add, mul).
  • SegmentTree class: Implements the segment tree structure with methods for modifyAdd, modifyMul, query, pushup, and pushdown.
  • Fancy class: The main class with methods append, addAll, multAll, and getIndex, using the SegmentTree to manage the sequence efficiently.

The Java and C++ implementations follow a similar structure, adapting the syntax and data structures accordingly. The core logic of using the segment tree for efficient updates and queries remains consistent across all three languages.