题目描述
市议会希望增加主要街道上建筑物的高度以吸引更多商业，但担心建设过快会导致资金耗尽，因此他们计划分阶段建设。
假设街道长度为nnn个单位，每个建筑物宽度为111个单位。在每个阶段，议会会选择两个端点（1≤a≤b≤100,0001 \leq a \leq b \leq 100,0001≤a≤b≤100,000），并将区间[a,b][a, b][a,b]内每栋建筑物的高度增加yyy个单位。例如，下面是变更前后的城市天际线：a=2,b=10,y=1a=2, b=10, y=1a=2,b=10,y=1。
随时间推移，跟踪建筑物高度变得相当复杂，因此需要你的帮助。
输入格式
输入文件最多包含888个测试用例。每个测试用例的第一行是一个正整数TTT，表示指令数量。接下来的TTT行（T≤100,000T \leq 100,000T≤100,000）是以下两种格式之一：
B a b y：建造指令 —— 将区间[a,b][a, b][a,b]内每栋建筑的高度增加yyy单位。Q a：查询指令 —— 输出此时建筑aaa的高度。
输入行总是合法的，即1≤a≤b≤100,0001 \leq a \leq b \leq 100,0001≤a≤b≤100,000。yyy是正整数，最多为1,0001,0001,000。假设在第一个阶段之前，所有建筑的高度均为000。输入以T=0T=0T=0结束。
输出格式
对于每个测试用例的每个查询指令，在一行中输出指定建筑的高度。
样例
输入
9 B 5 5 2 B 8 8 2 B 10 13 1 Q 8 B 8 13 1 Q 8 B 15 16 1 B 2 10 1 Q 8 0输出
2 3 4题目分析
本题的核心是：维护一个长度为100,000100,000100,000的数组（初始全为000），支持两种操作：
- 区间加：将区间[a,b][a, b][a,b]内的所有元素增加yyy。
- 单点查询：查询位置aaa的当前值。
直接模拟：对于每个B指令，遍历区间[a,b][a, b][a,b]逐个增加，时间复杂度为O(T⋅n)O(T \cdot n)O(T⋅n)，其中nnn为区间长度，最坏情况下n=105n=10^5n=105，T=105T=10^5T=105，总操作量可达101010^{10}1010，不可接受。
我们需要一种支持高效区间更新和单点查询的数据结构。
解题思路
差分数组 + 前缀和
差分数组的思想：设原数组为height[1..n]\textit{height}[1..n]height[1..n]，定义差分数组diff[i]=height[i]−height[i−1]\textit{diff}[i] = \textit{height}[i] - \textit{height}[i-1]diff[i]=height[i]−height[i−1]（约定height[0]=0\textit{height}[0]=0height[0]=0）。那么：
- 对原数组区间[a,b][a, b][a,b]增加yyy，等价于：
- diff[a] +=y\textit{diff}[a] \ += ydiff[a]+=y
- diff[b+1] −=y\textit{diff}[b+1] \ -= ydiff[b+1]−=y
- 查询原数组位置aaa的值，等价于求diff[1..a]\textit{diff}[1..a]diff[1..a]的前缀和：height[a]=∑i=1adiff[i]\textit{height}[a] = \sum_{i=1}^{a} \textit{diff}[i]height[a]=∑i=1adiff[i]
这样，每次更新是O(1)O(1)O(1)的，但查询需要O(n)O(n)O(n)计算前缀和，当查询很多时仍会超时。
树状数组（Fenwick Tree\texttt{Fenwick Tree}Fenwick Tree）
树状数组支持单点加和前缀和查询，均为O(logn)O(\log n)O(logn)。结合差分思想：
- 区间加[a,b][a, b][a,b]增加yyy：执行两次单点加：
add(a, y)和add(b+1, -y) - 单点查询aaa：执行前缀和查询
sum(a)
这样每次操作均为O(logN)O(\log N)O(logN)，N=100,000N=100,000N=100,000，总复杂度O(TlogN)O(T \log N)O(TlogN)，完全可接受。
算法流程
- 初始化大小为100,002100,002100,002的树状数组（因为b+1b+1b+1可能等于100,001100,001100,001）。
- 对于每个测试用例：
- 读入TTT，若T=0T=0T=0则结束。
- 循环TTT次：
- 读入指令类型。
- 若为
B，读入a,b,ya,b,ya,b,y，执行add(a, y)和add(b+1, -y)。 - 若为
Q，读入aaa，输出sum(a)。
- 每个测试用例结束后，重置树状数组（或直接覆盖）。
复杂度分析
- 时间复杂度：每个操作O(logN)O(\log N)O(logN)，总操作次数T≤105T \leq 10^5T≤105，故总复杂度O(TlogN)O(T \log N)O(TlogN)。
- 空间复杂度：O(N)O(N)O(N)，N=100,002N=100,002N=100,002。
代码实现
// Kool Konstructions// UVa ID: 12769// Verdict: Accepted// Submission Date: 2026-06-04// UVa Run Time: 0.080s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAX_N=100002;intbit[MAX_N];// 树状数组// 单点加voidadd(intidx,intval){while(idx<MAX_N){bit[idx]+=val;idx+=idx&-idx;}}// 前缀和intsum(intidx){intres=0;while(idx>0){res+=bit[idx];idx-=idx&-idx;}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;while(cin>>T&&T!=0){memset(bit,0,sizeof(bit));// 每个测试用例重置树状数组while(T--){charop;cin>>op;if(op=='B'){inta,b,y;cin>>a>>b>>y;add(a,y);add(b+1,-y);}else{// op == 'Q'inta;cin>>a;cout<<sum(a)<<'\n';}}}return0;}总结
本题的关键点在于：
- 将区间更新转化为差分数组的两个单点更新，再通过树状数组维护前缀和。
- 树状数组是实现单点加和前缀和的高效工具，代码简洁且常数小。
- 注意边界：b+1b+1b+1可能超出nnn，因此树状数组大小需要设为n+2n+2n+2。
这类“区间加、单点查询”问题是树状数组的经典应用场景。如果问题变为“区间加、区间查询”，则需要使用两个树状数组或线段树。掌握差分思想与树状数组的结合，可以高效解决许多区间维护问题。