本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AtCoder：E - Store Sales Management
【题目描述】
Takahashi works at the headquarters of a retail company that operates a chain of stores nationwide. The company runs a system that centrally manages the sales of each store.
There areN NNstores nationwide, each assigned a store number from1 11toN NN. For each storei ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N), an initial sales amountS i S_iSiis recorded.
For business analysis, Takahashi needs to process a total ofQ QQqueries of the following2 22types, in the given order.
- Type 1(
1 L R): Output the total sales amount of all stores whose store numbers are betweenL LLandR RRinclusive, that is,S L + S L + 1 + ⋯ + S R S_L + S_{L+1} + \cdots + S_RSL+SL+1+⋯+SR. - Type 2(
2 X V): Overwrite the sales amountS X S_XSXof storeX XXwithV VV. That is, setS X ← V S_X \leftarrow VSX←V.
For each Type 1 query, the total sales amount should be computed with all changes from previous Type 2 queries already applied.
Please find the answer to each Type 1 query on behalf of Takahashi.
【输入】
N NNQ QQ
S 1 S_1S1S 2 S_2S2… \ldots…S N S_NSN
q u e r y 1 \mathrm{query}_1query1
q u e r y 2 \mathrm{query}_2query2
⋮ \vdots⋮
q u e r y Q \mathrm{query}_QqueryQ
- The first line contains the number of storesN NNand the number of queriesQ QQ, separated by a space.
- The second line contains the initial sales amountsS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1,S2,…,SNof each store, separated by spaces.
- The followingQ QQlines each contain one of theQ QQqueries. Each query is distinguished by the leading integer indicating its type. Thei ii-th queryq u e r y i \mathrm{query}_iqueryiis given in one of the following formats:
- Type 1:
1 L R(compute the total sales amount of stores with numbers fromL LLtoR RRinclusive) - Type 2:
2 X V(overwrite the sales amount of storeX XXwithV VV)
【输出】
Each time a Type 1 query is processed, output the corresponding total sales amount on a single line.
【输入样例】
5 4 10 20 30 40 50 1 1 3 2 2 100 1 1 3 1 2 5【输出样例】
60 140 220【解题思路】
【算法标签】
#树状数组#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,q;// n: 数组长度，q: 操作次数ints[N],tr[N];// s: 原数组，tr: 树状数组// 获取x的最低位的1intlowbit(intx){returnx&-x;}// 树状数组更新：在位置x加上cvoidadd(intx,intc){for(inti=x;i<=n;i+=lowbit(i)){tr[i]+=c;}}// 树状数组查询：求前缀和[1, x]intquery(intx){intres=0;for(inti=x;i;i-=lowbit(i)){res+=tr[i];}returnres;}signedmain(){cin>>n>>q;// 读入数组长度和操作次数for(inti=1;i<=n;i++){cin>>s[i];// 读入数组元素add(i,s[i]);// 初始化树状数组}while(q--)// 处理每个操作{intop;cin>>op;// 读入操作类型if(op==1)// 查询操作{intl,r;cin>>l>>r;// 读入查询区间// 输出区间和：前缀和[r] - 前缀和[l-1]cout<<query(r)-query(l-1)<<endl;}else// 更新操作{intx,v;cin>>x>>v;// 读入位置和新的值add(x,v-s[x]);// 更新树状数组s[x]=v;// 更新原数组}}return0;}【运行结果】
5 4 10 20 30 40 50 1 1 3 60 2 2 100 1 1 3 140 1 2 5 220
