首页 > 试题广场 >

Tree Recovery

[编程题]Tree Recovery
  • 热度指数：2 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

输入描述:
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.


输出描述:
You need to answer all Q commands in order. One answer in a line.
示例1

输入

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出

4
55
9
15
算法知识视频讲解
开通博客
头像 hrdate
发表于 2020-07-06 21:01:41
先对原数组a进行差分，得到差分数组b，才对b[i]和b[i]*i分别维护一个树状数组tb和tc，而l到r的和变为[(r + 1) * sum(tb, r) - sum(tc, r)]-[(l + 1) * sum(tb, l) - sum(tc, l)]需要注意的是开vector<>后靠 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 威风镰鼬
发表于 2021-06-12 23:58:40
思路 线段树裸题，区间修改+区间查询，板子如下。需要注意的一个坑点就是读命令的时候不要漏掉换行符。（个人码风习惯把int改成ll，各位还是要注意别爆了） 代码 #include<bits/stdc++.h> #define int ll using namespace std; type 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

线段树 树状数组
上传者：牛客303862号
难度：
0条回答 19浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Tree Recovery

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号