acwing 243. 一个简单的整数问题2 树状数组 线段树
2024-09-04 20:38:43
地址 https://www.acwing.com/problem/content/description/244/
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：
1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”，表示询问 数列中第 l~r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
≤N,M≤,
|d|≤,
|A[i]|≤
输入样例： Q
Q
Q
C
Q
输出样例：
解答
线段树模板 与上一题几乎一摸一样的板子 可以解决
可以说线段树就是解决此类问题的方案 缺点是相对树状数组 代码稍多
#include <iostream>
#include <algorithm>
#include <string> using namespace std; const int maxn = 1e5 + ;
int n;
int a[maxn];
int q; struct node {
int l, r;
long long sum, lazy;
void update(long long x) {
sum += 1ll * (r - l + )*x;
lazy += x;
}
}tree[maxn*]; void push_up(int x) {
tree[x].sum = tree[x << ].sum + tree[x << | ].sum;
} void push_down(int x)
{
int lazyval = tree[x].lazy;
if (lazyval) {
tree[x << ].update(lazyval);
tree[x << | ].update(lazyval);
tree[x].lazy = ;
} } void build(int x, int l, int r) {
tree[x].l = l; tree[x].r = r;
tree[x].sum = tree[x].lazy = ;
if (l == r) {
tree[x].sum = a[l];
}
else {
int mid = (l + r) / ;
build(x << , l, mid);
build(x << | , mid + , r);
push_up(x);
}
} void update(int x, int l, int r, long long val)
{
int L = tree[x].l, R = tree[x].r;
if (l <= L && R <= r) {
tree[x].update(val);
}
else {
push_down(x);
int mid = (L + R) / ;
if (mid >= l) update(x << , l, r, val);
if (r > mid) update(x << | , l, r, val);
push_up(x);
}
} long long query(int x, int l, int r)
{
int L = tree[x].l, R = tree[x].r;
if (l <= L && R <= r) {
return tree[x].sum;
}
else {
push_down(x);
long long ans = ;
int mid = (L + R) / ;
if (mid >= l) ans += query(x << , l, r);
if (r > mid) ans += query(x << | , l, r);
push_up(x);
return ans;
}
} int main()
{
cin >> n >> q;
for (int i = ; i <= n; i++) {
cin >> a[i];
}
build(, , n); for (int i = ; i <= q; i++) {
string s;
int l, r, d, q;
cin >> s;
if (s == "Q") {
cin >> l>>r;
cout << query(, l, r) << endl;
}
else {
cin >> l >> r >> d;
update(, l, r, d);
}
} return ;
}
线段树
线段树的 区间加 区间和查询解决方案 要使用差分数组
// 1111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
// #include <iostream>
#include <string>
#include <algorithm> using namespace std; const int N = ; typedef long long LL; int n, m;
int a[N];
LL tree1[N]; //b[i]前缀和 差分数组
LL tree2[N]; //b[i]*i前缀和 int lowbit(int x) {
return x & -x;
} void add(LL tr[], int x, LL c) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
} LL sum(LL tr[], int x) {
LL res = ;
for(int i = x;i;i-=lowbit(i)) res += tr[i]; return res;
} LL prefix_sum(int x) {
return sum(tree1, x)*(x + ) - sum(tree2, x);
} int main()
{
scanf("%d%d",&n,&m);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= n; i++) {
int b = a[i] - a[i - ];
add(tree1, i, (LL)b);
add(tree2, i, (LL)b*i);
} while (m--) {
char op[];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q') {
printf("%lld\n",prefix_sum(r)-prefix_sum(l-));
}
else {
scanf("%d", &d);
//a[l]+=d
add(tree1, l, d);
add(tree2, l, l*d);
// a[r+1] -= d
add(tree1, r + , -d);
add(tree2, r + , (r + )*-d);
}
} return ;
}
最新文章
- The Java Enum: A Singleton Pattern [reproduced]
- Scoped CSS规范草案
- setTimeout 和 setInterval 的区别
- 小小border用处多
- springboot使用之一：连接生产数据库，添加连接池
- HDU3359 Kind of a Blur(高斯消元)
- 20145334赵文豪 《Java程序设计》第1周学习总结
- Rstudio使用记录
- SQL Server 2005导入Excel表问题
- Custom ReadOnlyProperty【PluraSight】
- 1562: [NOI2009]变换序列 - BZOJ
- linux系统 备份与还原
- [jAudio] JAVA上经典特征提取工具
- Luogu4195 【模板】exBSGS（exBSGS）
- 洛谷P1182 数列分段【二分】【贪心】
- Grunt教程——安装Grunt
- mongodb基础学习13-聚集aggregate操作
- js中图片获取src的正则
- 一文搞定 Mybatis 的应用
- linux convert命令安装及使用