C++ / 动态累计账单 算法挑战

动态累计账单

在没有分步提示的新场景中，独立应用本单元的数据结构。

需求与输入输出

第一行 n q，随后 n 个初始整数。ADD i delta 修改第 i 项；SUM r 查询前 r 项之和，允许 r=0。初值和增量绝对值不超过 10⁶。每次 SUM 输出一行。

使用 C++17。输入符合协议，编号从 1 开始；除特别说明外，n、q 均不超过 100000。不要输出额外提示语。

样例输入

3 3
1 2 3
SUM 2
ADD 1 4
SUM 3

样例输出

3
10

验收要求

• 正确处理单元素、空结构或无匹配情况。
• 更新后查询反映最新状态；多个测试之间不共享状态。
• 累计量使用 long long。

实现建议

用树状数组维护累计信息；更新和查询都应为 O(log n)，查询 0 返回 0。

先手工推演样例，再独立编写实现。通过测试后需正式提交，才计入编程成果。