UVa 12769 Kool Konstructions

题目描述市议会希望增加主要街道上建筑物的高度以吸引更多商业但担心建设过快会导致资金耗尽因此他们计划分阶段建设。假设街道长度为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个单位。例如下面是变更前后的城市天际线a2,b10,y1a2, b10, y1a2,b10,y1。随时间推移跟踪建筑物高度变得相当复杂因此需要你的帮助。输入格式输入文件最多包含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。输入以T0T0T0结束。输出格式对于每个测试用例的每个查询指令在一行中输出指定建筑的高度。样例输入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为区间长度最坏情况下n105n10^5n105T105T10^5T105总操作量可达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]ydiff[b1] −y\textit{diff}[b1] \ - ydiff[b1]−y查询原数组位置aaa的值等价于求diff[1..a]\textit{diff}[1..a]diff[1..a]的前缀和height[a]∑i1adiff[i]\textit{height}[a] \sum_{i1}^{a} \textit{diff}[i]height[a]∑i1a​diff[i]这样每次更新是O(1)O(1)O(1)的但查询需要O(n)O(n)O(n)计算前缀和当查询很多时仍会超时。树状数组Fenwick Tree\texttt{Fenwick Tree}Fenwick Tree树状数组支持单点加和前缀和查询均为O(log⁡n)O(\log n)O(logn)。结合差分思想区间加[a,b][a, b][a,b]增加yyy执行两次单点加add(a, y)和add(b1, -y)单点查询aaa执行前缀和查询sum(a)这样每次操作均为O(log⁡N)O(\log N)O(logN)N100,000N100,000N100,000总复杂度O(Tlog⁡N)O(T \log N)O(TlogN)完全可接受。算法流程初始化大小为100,002100,002100,002的树状数组因为b1b1b1可能等于100,001100,001100,001。对于每个测试用例读入TTT若T0T0T0则结束。循环TTT次读入指令类型。若为B读入a,b,ya,b,ya,b,y执行add(a, y)和add(b1, -y)。若为Q读入aaa输出sum(a)。每个测试用例结束后重置树状数组或直接覆盖。复杂度分析时间复杂度每个操作O(log⁡N)O(\log N)O(logN)总操作次数T≤105T \leq 10^5T≤105故总复杂度O(Tlog⁡N)O(T \log N)O(TlogN)。空间复杂度O(N)O(N)O(N)N100,002N100,002N100,002。代码实现// Kool Konstructions// UVa ID: 12769// Verdict: Accepted// Submission Date: 2026-06-04// UVa Run Time: 0.080s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_N100002;intbit[MAX_N];// 树状数组// 单点加voidadd(intidx,intval){while(idxMAX_N){bit[idx]val;idxidx-idx;}}// 前缀和intsum(intidx){intres0;while(idx0){resbit[idx];idx-idx-idx;}returnres;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;while(cinTT!0){memset(bit,0,sizeof(bit));// 每个测试用例重置树状数组while(T--){charop;cinop;if(opB){inta,b,y;cinaby;add(a,y);add(b1,-y);}else{// op Qinta;cina;coutsum(a)\n;}}}return0;}总结本题的关键点在于将区间更新转化为差分数组的两个单点更新再通过树状数组维护前缀和。树状数组是实现单点加和前缀和的高效工具代码简洁且常数小。注意边界b1b1b1可能超出nnn因此树状数组大小需要设为n2n2n2。这类“区间加、单点查询”问题是树状数组的经典应用场景。如果问题变为“区间加、区间查询”则需要使用两个树状数组或线段树。掌握差分思想与树状数组的结合可以高效解决许多区间维护问题。