LeetCode 题解工作台
奇妙序列
请你实现三个 API append ， addAll 和 multAll 来实现奇妙序列。 请实现 Fancy 类 ： Fancy() 初始化一个空序列对象。 void append(val) 将整数 val 添加在序列末尾。 void addAll(inc) 将所有序列中的现有数值都增加 inc …
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数学·结合·design
答案摘要
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 `log(width)`。更新某个元素的值，只需要更新 `log(width)` 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。 - 线段树的每个节点代表一个区间；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·design 题型思路
题目描述
请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。
请实现 Fancy 类 ：
Fancy()初始化一个空序列对象。void append(val)将整数val添加在序列末尾。void addAll(inc)将所有序列中的现有数值都增加inc。void multAll(m)将序列中的所有现有数值都乘以整数m。int getIndex(idx)得到下标为idx处的数值（下标从 0 开始），并将结果对109 + 7取余。如果下标大于等于序列的长度，请返回-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 <= 1000 <= idx <= 105- 总共最多会有
105次对append，addAll，multAll和getIndex的调用。
解题思路
方法一：线段树
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 log(width)。更新某个元素的值，只需要更新 log(width) 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如
[1, N]； - 线段树的每个叶子节点代表一个长度为 1 的元区间
[x, x]； - 对于每个内部节点
[l, r]，它的左儿子是[l, mid]，右儿子是[mid + 1, r], 其中mid = ⌊(l + r) / 2⌋(即向下取整)。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity per operation is O(1) for append, addAll, multAll, and getIndex due to cumulative tracking. Space complexity is O(n) for storing the sequence and cumulative multipliers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate optimizes getIndex using cumulative multipliers instead of iterating over the entire sequence.
- question_mark
Candidate identifies that naive full sequence updates will exceed time limits with 10^5 operations.
- question_mark
Candidate uses modular arithmetic to handle potential integer overflow and maintain correct results.
常见陷阱
外企场景- error
Updating every element on addAll or multAll leads to TLE for large sequences.
- error
Neglecting modular arithmetic can result in integer overflow and incorrect answers.
- error
Incorrectly tracking cumulative multipliers or sums may return wrong getIndex values.
进阶变体
外企场景- arrow_right_alt
Implement a similar sequence API but supporting range queries and updates instead of single-element getIndex.
- arrow_right_alt
Optimize Fancy sequence operations for floating-point numbers with precision constraints.
- arrow_right_alt
Design a Fancy sequence variant that supports undoing the last operation efficiently.