1622. 花式序列

Hard

题目描述

编写一个 API 来生成使用 append、addAll 和 multAll 操作的花式序列。

实现 Fancy 类：

Fancy() 用一个空序列初始化对象。
void append(val) 将整数 val 追加到序列的末尾。
void addAll(inc) 将序列中所有现有值增加整数 inc。
void multAll(m) 将序列中所有现有值乘以整数 m。
int getIndex(idx) 获取序列中索引 idx（0 索引）处的当前值模 10^9 + 7。如果索引大于或等于序列的长度，则返回 -1。

示例 1：

输入
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释
Fancy fancy = new Fancy();
fancy.append(2);   // 花式序列：[2]
fancy.addAll(3);   // 花式序列：[2+3] -> [5]
fancy.append(7);   // 花式序列：[5, 7]
fancy.multAll(2);  // 花式序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 花式序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 花式序列：[13, 17, 10]
fancy.multAll(2);  // 花式序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

约束条件：

1 <= val, inc, m <= 100
0 <= idx <= 10^5
总共最多调用 10^5 次 append、addAll、multAll 和 getIndex。

解题思路

这道题的核心挑战是如何高效地处理全局操作（addAll 和 multAll）而不实际更新数组中的每个元素。

关键思路：

延迟计算：不立即对数组中的每个元素执行操作，而是记录这些操作的累积效果
维护累积状态：使用两个数组记录每个时间点的状态
- mult[]：记录从序列开始到当前时间点的累积乘法因子
- add[]：记录调整后的累积加法值

核心观察： 对于在时间 t 添加的元素 val，当前值可以表示为： result = (val * mult_current / mult_t + add_current - add_t) % MOD

其中 mult_current / mult_t 表示从时间 t 到现在的乘法倍数。由于需要模运算，使用模逆元来处理除法。

算法步骤：

初始化时，mult[0] = 1, add[0] = 0
append(val)：直接添加到数组，记录添加时的时间点
addAll(inc)：更新 add 数组，add[t] = (add[t-1] + inc) % MOD
multAll(m)：更新两个数组，mult[t] = (mult[t-1] * m) % MOD, add[t] = (add[t-1] * m) % MOD
getIndex(idx)：使用公式计算当前值

这种方法避免了每次全局操作都要遍历整个数组，时间复杂度从 O(n) 降到 O(1)。

代码实现

class Fancy {
private:
    static const int MOD = 1000000007;
    vector<int> nums;
    vector<long long> mult, add;
    
    long long power(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }
    
    long long modInverse(long long a, long long mod) {
        return power(a, mod - 2, mod);
    }
    
public:
    Fancy() {
        mult.push_back(1);
        add.push_back(0);
    }
    
    void append(int val) {
        nums.push_back(val);
    }
    
    void addAll(int inc) {
        long long lastAdd = add.back();
        long long lastMult = mult.back();
        add.push_back((lastAdd + inc) % MOD);
        mult.push_back(lastMult);
    }
    
    void multAll(int m) {
        long long lastAdd = add.back();
        long long lastMult = mult.back();
        add.push_back((lastAdd * m) % MOD);
        mult.push_back((lastMult * m) % MOD);
    }
    
    int getIndex(int idx) {
        if (idx >= nums.size()) {
            return -1;
        }
        
        long long val = nums[idx];
        long long multNow = mult.back();
        long long addNow = add.back();
        long long multThen = mult[idx];
        long long addThen = add[idx];
        
        long long result = (val * multNow % MOD * modInverse(multThen, MOD) % MOD + 
                           (addNow - addThen + MOD) % MOD) % MOD;
        return (int)result;
    }
};

class Fancy:

    def __init__(self):
        self.MOD = 10**9 + 7
        self.nums = []
        self.mult = [1]
        self.add = [0]
    
    def power(self, base, exp, mod):
        result = 1
        while exp > 0:
            if exp % 2 == 1:
                result = (result * base) % mod
            base = (base * base) % mod
            exp //= 2
        return result
    
    def mod_inverse(self, a, mod):
        return self.power(a, mod - 2, mod)

    def append(self, val: int) -> None:
        self.nums.append(val)

    def addAll(self, inc: int) -> None:
        last_add = self.add[-1]
        last_mult = self.mult[-1]
        self.add.append((last_add + inc) % self.MOD)
        self.mult.append(last_mult)

    def multAll(self, m: int) -> None:
        last_add = self.add[-1]
        last_mult = self.mult[-1]
        self.add.append((last_add * m) % self.MOD)
        self.mult.append((last_mult * m) % self.MOD)

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.nums):
            return -1
        
        val = self.nums[idx]
        mult_now = self.mult[-1]
        add_now = self.add[-1]
        mult_then = self.mult[idx]
        add_then = self.add[idx]
        
        result = (val * mult_now % self.MOD * self.mod_inverse(mult_then, self.MOD) % self.MOD + 
                 (add_now - add_then + self.MOD) % self.MOD) % self.MOD
        return result

public class Fancy {
    private const int MOD = 1000000007;
    private List<int> nums;
    private List<long> mult, add;
    
    private long Power(long baseVal, long exp, long mod) {
        long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * baseVal) % mod;
            }
            baseVal = (baseVal * baseVal) % mod;
            exp /= 2;
        }
        return result;
    }
    
    private long ModInverse(long a, long mod) {
        return Power(a, mod - 2, mod);
    }

    public Fancy() {
        nums = new List<int>();
        mult = new List<long> { 1 };
        add = new List<long> { 0 };
    }
    
    public void Append(int val) {
        nums.Add(val);
    }
    
    public void AddAll(int inc) {
        long lastAdd = add[add.Count - 1];
        long lastMult = mult[mult.Count - 1];
        add.Add((lastAdd + inc) % MOD);
        mult.Add(lastMult);
    }
    
    public void MultAll(int m) {
        long lastAdd = add[add.Count - 1];
        long lastMult = mult[mult.Count - 1];
        add.Add((lastAdd * m) % MOD);
        mult.Add((lastMult * m) % MOD);
    }
    
    public int GetIndex(int idx) {
        if (idx >= nums.Count) {
            return -1;
        }
        
        long val = nums[idx];
        long multNow = mult[mult.Count - 1];
        long addNow = add[add.Count - 1];
        long multThen = mult[idx];
        long addThen = add[idx];
        
        long result = (val * multNow % MOD * ModInverse(multThen, MOD) % MOD + 
                      (addNow - addThen + MOD) % MOD) % MOD;
        return (int)result;
    }
}

var Fancy = function() {
    this.sequence = [];
    this.mult = 1;
    this.add = 0;
    this.MOD = 1000000007;
};

Fancy.prototype.append = function(val) {
    // Store the inverse transformation to get back to original value
    const invMult = this.modInverse(this.mult);
    const originalVal = ((val - this.add + this.MOD) * invMult) % this.MOD;
    this.sequence.push(originalVal);
};

Fancy.prototype.addAll = function(inc) {
    this.add = (this.add + inc) % this.MOD;
};

Fancy.prototype.multAll = function(m) {
    this.mult = (this.mult * m) % this.MOD;
    this.add = (this.add * m) % this.MOD;
};

Fancy.prototype.getIndex = function(idx) {
    if (idx >= this.sequence.length) return -1;
    return (this.sequence[idx] * this.mult + this.add) % this.MOD;
};

Fancy.prototype.modInverse = function(a) {
    return this.power(a, this.MOD - 2);
};

Fancy.prototype.power = function(base, exp) {
    let result = 1;
    base %= this.MOD;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % this.MOD;
        base = (base * base) % this.MOD;
        exp >>= 1;
    }
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
append	O(1)	O(1)
addAll	O(1)	O(1)
multAll	O(1)	O(1)
getIndex	O(log MOD)	O(1)
总体空间复杂度	-	O(n + m)

其中 n 是 append 操作的次数，m 是 addAll 和 multAll 操作的总次数。getIndex 的时间复杂度为 O(log MOD) 是因为需要计算模逆元。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析