# Fancy Sequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/fancy-sequence)
Canonical: https://scaleengineer.com/dsa/problems/fancy-sequence
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Segment Tree
---
## Problem
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`.

# Approaches
## Brute Force Simulation
This approach directly simulates the described operations using a list. For `append`, we add the element to the list. For `addAll` and `multAll`, we iterate through the entire list and apply the operation to each element individually. `getIndex` is a simple lookup.
**Time:** - `append(val)`: O(1) amortized time.
- `addAll(inc)`: O(N) time, where N is the current size of the sequence.
- `multAll(m)`: O(N) time.
- `getIndex(idx)`: O(1) time. · **Space:** O(N), where N is the number of elements in the sequence (i.e., the number of `append` calls).
**Pros:** Very simple to understand and implement.; `append` and `getIndex` operations are fast.
**Cons:** The `addAll` and `multAll` operations are very slow, with a time complexity linear in the size of the sequence.; This approach will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs, given the problem constraints.
### Explanation
In this naive approach, we maintain a list of numbers, for example, a `java.util.ArrayList<Long>`. The `append` operation is efficient, simply adding an element to the end of the list. However, the `addAll` and `multAll` operations require us to traverse the entire list, updating each element one by one. While simple to conceive and implement, this leads to poor performance when the sequence is long and these update operations are called frequently.

```java
import java.util.ArrayList;
import java.util.List;

class Fancy {
    private List<Long> seq;
    private final int MOD = 1_000_000_007;

    public Fancy() {
        seq = new ArrayList<>();
    }
    
    public void append(int val) {
        seq.add((long) val);
    }
    
    public void addAll(int inc) {
        for (int i = 0; i < seq.size(); i++) {
            seq.set(i, (seq.get(i) + inc) % MOD);
        }
    }
    
    public void multAll(int m) {
        for (int i = 0; i < seq.size(); i++) {
            seq.set(i, (seq.get(i) * m) % MOD);
        }
    }
    
    public int getIndex(int idx) {
        if (idx >= seq.size()) {
            return -1;
        }
        return seq.get(idx).intValue();
    }
}
```
### Algorithm
- Use a dynamic array (like `ArrayList` in Java) to store the numbers of the sequence.
- `append(val)`: Add the integer `val` to the end of the list.
- `addAll(inc)`: Iterate through every element in the list and add `inc` to it.
- `multAll(m)`: Iterate through every element in the list and multiply it by `m`. Remember to take the result modulo `10^9 + 7` at each step to prevent overflow.
- `getIndex(idx)`: If the index is valid, return the element at that index. Otherwise, return -1.

## Lazy Propagation with Modular Arithmetic
A highly efficient approach is to use lazy propagation. Instead of updating every element for `addAll` and `multAll`, we track the cumulative effect of these operations using two variables: a multiplicative factor `mult` and an additive factor `add`. When a value is appended, it's 'normalized' by reversing the current cumulative operations. When `getIndex` is called, we apply the current cumulative operations to the stored normalized value to get the correct result. This makes `addAll`, `multAll`, and `getIndex` O(1) operations.
**Time:** - `append(val)`: O(log MOD) due to the modular inverse calculation (which uses modular exponentiation).
- `addAll(inc)`: O(1).
- `multAll(m)`: O(1).
- `getIndex(idx)`: O(1). · **Space:** O(N), where N is the number of `append` calls, to store the normalized sequence.
**Pros:** Extremely efficient, with `addAll`, `multAll`, and `getIndex` all being constant time operations.; This approach will pass within the time limits for the given constraints.
**Cons:** The logic is more complex, involving modular arithmetic, modular inverse, and the concept of normalizing values.; Requires careful implementation to handle potential overflows by using `long` for intermediate calculations and applying the modulo operator correctly.
### Explanation
The key insight is that any sequence of additions and multiplications can be combined into a single linear transformation of the form `f(x) = x * M + A`. We can maintain these cumulative factors, `mult` (M) and `add` (A), globally.

- When `addAll(inc)` is called, the transformation `x*mult + add` becomes `(x*mult + add) + inc`, which simplifies to `x*mult + (add + inc)`. So, we just update `add`.
- When `multAll(m)` is called, `x*mult + add` becomes `(x*mult + add) * m`, which is `x*(mult*m) + (add*m)`. We update both `mult` and `add`.

- The tricky part is `append(val)`. A new value `val` should not be affected by past operations. We store a 'base' value `v_base` such that when the current global transformation is applied, it yields `val`. That is, `v_base * mult + add = val`. Solving for `v_base`, we get `v_base = (val - add) * modInverse(mult)`. This is the value we store.

- For `getIndex(idx)`, we retrieve the stored `v_base` and apply the current global transformation: `(v_base * mult + add) % MOD`.

This requires calculating the modular multiplicative inverse, which can be done efficiently using Fermat's Little Theorem (`a^(p-2) mod p`) since the modulus `10^9 + 7` is prime.

```java
import java.util.ArrayList;
import java.util.List;

class Fancy {
    private final long MOD = 1_000_000_007L;
    private List<Long> seq;
    private long add; // Cumulative additive factor
    private long mult; // Cumulative multiplicative factor

    public Fancy() {
        this.seq = new ArrayList<>();
        this.add = 0L;
        this.mult = 1L;
    }

    // Modular exponentiation to calculate (base^exp) % MOD
    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    // Modular multiplicative inverse using Fermat's Little Theorem
    private long modInverse(long n) {
        return power(n, MOD - 2);
    }

    public void append(int val) {
        long tempVal = val;
        // Normalize the value before storing
        // We need v_base such that: v_base * mult + add = val
        // v_base = (val - add) / mult
        tempVal = (tempVal - add + MOD) % MOD; // Handle negative results from subtraction
        tempVal = (tempVal * modInverse(mult)) % MOD;
        seq.add(tempVal);
    }

    public void addAll(int inc) {
        add = (add + inc) % MOD;
    }

    public void multAll(int m) {
        mult = (mult * m) % MOD;
        add = (add * m) % MOD;
    }

    public int getIndex(int idx) {
        if (idx >= seq.size()) {
            return -1;
        }
        // Apply the cumulative transformations to the stored base value
        long val = seq.get(idx);
        val = (val * mult) % MOD;
        val = (val + add) % MOD;
        return (int) val;
    }
}
```
### Algorithm
- Maintain a list `seq` for the numbers, and two global state variables, `add` (initially 0) and `mult` (initially 1).
- These variables track the cumulative transformation `x -> x * mult + add`.
- `append(val)`: To counteract the global transformations that haven't been applied to `val`, store a 'normalized' value. Calculate `v_base = (val - add) * modInverse(mult)` and append `v_base` to `seq`. All calculations are modulo `10^9 + 7`.
- `addAll(inc)`: Update the additive factor: `add = (add + inc) % MOD`.
- `multAll(m)`: Update both factors: `mult = (mult * m) % MOD` and `add = (add * m) % MOD`.
- `getIndex(idx)`: Retrieve the normalized value `v_base` from `seq`. Apply the current global transformation to get the final value: `result = (v_base * mult + add) % MOD`.
- A helper function for modular exponentiation is needed to compute the modular multiplicative inverse.

# Solutions
### Java

```java
class Node { Node left ; Node right ; int l ; int r ; int mid ; long v ; long add ; long mul = 1 ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e5 + 1 ); private static final int MOD = ( int ) 1 e9 + 7 ; public SegmentTree () { } public void modifyAdd ( int l , int r , int inc ) { modifyAdd ( l , r , inc , root ); } public void modifyAdd ( int l , int r , int inc , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = ( node . v + ( node . r - node . l + 1 ) * inc ) % MOD ; node . add = ( node . add + inc ) % MOD ; return ; } pushdown ( node ); if ( l <= node . mid ) { modifyAdd ( l , r , inc , node . left ); } if ( r > node . mid ) { modifyAdd ( l , r , inc , node . right ); } pushup ( node ); } public void modifyMul ( int l , int r , int m ) { modifyMul ( l , r , m , root ); } public void modifyMul ( int l , int r , int m , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v = ( node . v * m ) % MOD ; node . add = ( node . add * m ) % MOD ; node . mul = ( node . mul * m ) % MOD ; return ; } pushdown ( node ); if ( l <= node . mid ) { modifyMul ( l , r , m , node . left ); } if ( r > node . mid ) { modifyMul ( l , r , m , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return ( int ) node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v = ( v + query ( l , r , node . left )) % MOD ; } if ( r > node . mid ) { v = ( v + query ( l , r , node . right )) % MOD ; } return v ; } public void pushup ( Node node ) { node . v = ( node . left . v + node . right . v ) % MOD ; } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 || node . mul != 1 ) { Node left = node . left , right = node . right ; left . v = ( left . v * node . mul + ( left . r - left . l + 1 ) * node . add ) % MOD ; right . v = ( right . v * node . mul + ( right . r - right . l + 1 ) * node . add ) % MOD ; left . add = ( left . add * node . mul + node . add ) % MOD ; right . add = ( right . add * node . mul + node . add ) % MOD ; left . mul = ( left . mul * node . mul ) % MOD ; right . mul = ( right . mul * node . mul ) % MOD ; node . add = 0 ; node . mul = 1 ; } } } class Fancy { private int n ; private SegmentTree tree = new SegmentTree (); public Fancy () { } public void append ( int val ) { ++ n ; tree . modifyAdd ( n , n , val ); } public void addAll ( int inc ) { tree . modifyAdd ( 1 , n , inc ); } public void multAll ( int m ) { tree . modifyMul ( 1 , n , m ); } public int getIndex ( int idx ) { return idx >= n ? - 1 : tree . query ( idx + 1 , idx + 1 ); } } /** * Your Fancy object will be instantiated and called as such: * Fancy obj = new Fancy(); * obj.append(val); * obj.addAll(inc); * obj.multAll(m); * int param_4 = obj.getIndex(idx); */
```

### CPP

```cpp
const int MOD = 1e9 + 7 ; class Node { public: Node * left ; Node * right ; int l ; int r ; int mid ; long long v ; long long add ; long long mul ; Node ( int l , int r ) { this -> l = l ; this -> r = r ; this -> mid = ( l + r ) >> 1 ; this -> left = this -> right = nullptr ; v = add = 0 ; mul = 1 ; } }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node ( 1 , 1e5 + 1 ); } void modifyAdd ( int l , int r , int inc ) { modifyAdd ( l , r , inc , root ); } void modifyAdd ( int l , int r , int inc , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v = ( node -> v + ( node -> r - node -> l + 1 ) * inc ) % MOD ; node -> add = ( node -> add + inc ) % MOD ; return ; } pushdown ( node ); if ( l <= node -> mid ) modifyAdd ( l , r , inc , node -> left ); if ( r > node -> mid ) modifyAdd ( l , r , inc , node -> right ); pushup ( node ); } void modifyMul ( int l , int r , int m ) { modifyMul ( l , r , m , root ); } void modifyMul ( int l , int r , int m , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v = ( node -> v * m ) % MOD ; node -> add = ( node -> add * m ) % MOD ; node -> mul = ( node -> mul * m ) % MOD ; return ; } pushdown ( node ); if ( l <= node -> mid ) modifyMul ( l , r , m , node -> left ); if ( r > node -> mid ) modifyMul ( l , r , m , node -> right ); pushup ( node ); } int query ( int l , int r ) { return query ( l , r , root ); } int query ( int l , int r , Node * node ) { if ( l > r ) return 0 ; if ( node -> l >= l && node -> r <= r ) return node -> v ; pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) v = ( v + query ( l , r , node -> left )) % MOD ; if ( r > node -> mid ) v = ( v + query ( l , r , node -> right )) % MOD ; return v ; } void pushup ( Node * node ) { node -> v = ( node -> left -> v + node -> right -> v ) % MOD ; } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node ( node -> l , node -> mid ); if ( ! node -> right ) node -> right = new Node ( node -> mid + 1 , node -> r ); if ( node -> add || node -> mul != 1 ) { long add = node -> add , mul = node -> mul ; Node * left = node -> left ; Node * right = node -> right ; left -> v = ( left -> v * mul + ( left -> r - left -> l + 1 ) * add ) % MOD ; right -> v = ( right -> v * mul + ( right -> r - right -> l + 1 ) * add ) % MOD ; left -> add = ( left -> add * mul + add ) % MOD ; right -> add = ( right -> add * mul + add ) % MOD ; left -> mul = ( left -> mul * mul ) % MOD ; right -> mul = ( right -> mul * mul ) % MOD ; node -> add = 0 ; node -> mul = 1 ; } } }; class Fancy { public: int n ; SegmentTree * tree ; Fancy () { n = 0 ; tree = new SegmentTree (); } void append ( int val ) { ++ n ; tree -> modifyAdd ( n , n , val ); } void addAll ( int inc ) { tree -> modifyAdd ( 1 , n , inc ); } void multAll ( int m ) { tree -> modifyMul ( 1 , n , m ); } int getIndex ( int idx ) { return idx >= n ? - 1 : tree -> query ( idx + 1 , idx + 1 ); } }; /** * Your Fancy object will be instantiated and called as such: * Fancy* obj = new Fancy(); * obj->append(val); * obj->addAll(inc); * obj->multAll(m); * int param_4 = obj->getIndex(idx); */
```

### Python

```python
MOD = int ( 1e9 + 7 ) class Node : def __init__ ( self , l , r ): self . left = None self . right = None self . l = l self . r = r self . mid = ( l + r ) >> 1 self . v = 0 self . add = 0 self . mul = 1 class SegmentTree : def __init__ ( self ): self . root = Node ( 1 , int ( 1e5 + 1 )) def modifyAdd ( self , l , r , inc , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v = ( node . v + ( node . r - node . l + 1 ) * inc ) % MOD node . add += inc return self . pushdown ( node ) if l <= node . mid : self . modifyAdd ( l , r , inc , node . left ) if r > node . mid : self . modifyAdd ( l , r , inc , node . right ) self . pushup ( node ) def modifyMul ( self , l , r , m , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v = ( node . v * m ) % MOD node . add = ( node . add * m ) % MOD node . mul = ( node . mul * m ) % MOD return self . pushdown ( node ) if l <= node . mid : self . modifyMul ( l , r , m , node . left ) if r > node . mid : self . modifyMul ( l , r , m , node . right ) self . pushup ( node ) def query ( self , l , r , node = None ): if l > r : return 0 if node is None : node = self . root if node . l >= l and node . r <= r : return node . v self . pushdown ( node ) v = 0 if l <= node . mid : v = ( v + self . query ( l , r , node . left )) % MOD if r > node . mid : v = ( v + self . query ( l , r , node . right )) % MOD return v def pushup ( self , node ): node . v = ( node . left . v + node . right . v ) % MOD def pushdown ( self , node ): if node . left is None : node . left = Node ( node . l , node . mid ) if node . right is None : node . right = Node ( node . mid + 1 , node . r ) left , right = node . left , node . right if node . add != 0 or node . mul != 1 : left . v = ( left . v * node . mul + ( left . r - left . l + 1 ) * node . add ) % MOD right . v = ( right . v * node . mul + ( right . r - right . l + 1 ) * node . add ) % MOD left . add = ( left . add * node . mul + node . add ) % MOD right . add = ( right . add * node . mul + node . add ) % MOD left . mul = ( left . mul * node . mul ) % MOD right . mul = ( right . mul * node . mul ) % MOD node . add = 0 node . mul = 1 class Fancy : def __init__ ( self ): self . n = 0 self . tree = SegmentTree () def append ( self , val : int ) -> None : self . n += 1 self . tree . modifyAdd ( self . n , self . n , val ) def addAll ( self , inc : int ) -> None : self . tree . modifyAdd ( 1 , self . n , inc ) def multAll ( self , m : int ) -> None : self . tree . modifyMul ( 1 , self . n , m ) def getIndex ( self , idx : int ) -> int : return - 1 if idx >= self . n else self . tree . query ( idx + 1 , idx + 1 ) # Your Fancy object will be instantiated and called as such: # obj = Fancy() # obj.append(val) # obj.addAll(inc) # obj.multAll(m) # param_4 = obj.getIndex(idx)
```