题目如下
题目描述
如题,已知一个数列,你需要进行下面两种操作:
将某区间每一个数加上 kk。
求出某区间每一个数的和。
输入格式
第一行包含两个整数 n, mn,m,分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数,表示一个操作,具体如下:
1 x y k:将区间 [x, y][x,y] 内每个数加上 kk。
2 x y:输出区间 [x, y][x,y] 内每个数的和。
输出格式
输出包含若干行整数,即为所有操作 2 的结果。
输入输出样例
输入 #1复制
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出 #1复制
11
8
20
说明/提示
对于n,m<=1e5
所有元素绝对值之和小于1e18.
#define _CRT_SECURE_NO_WARNINGS
#define lowbit(x) ((x) & - (x))
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<deque>
#include<queue>
#include<map>
#include<cstdio>
using namespace std;
long long n, m, x, y, add;
const int N = 1e5 + 5;
int ch[N];
struct tr
{
int l, r;
long long value;
int tag;
}tree[4 * N];
void push_up(int pos) { tree[pos].value = tree[pos * 2].value + tree[pos * 2 + 1].value; }
void bulit(int pos, int s, int e)
{
tree[pos].l = s, tree[pos].r = e;
if (s == e)
{
tree[pos].value = ch[s];
return;
}
int mid = (tree[pos].l + tree[pos].r) / 2;
bulit(pos * 2, s, mid);
bulit(pos * 2 + 1, mid + 1, e);
push_up(pos);
}
void addtag(int pos)
{
tree[pos].tag += add;
tree[pos].value += tree[pos].tag * (tree[pos].r - tree[pos].l + 1);
}
void push_down(int pos)
{
if(tree[pos].tag)
{
addtag(pos * 2), addtag(pos * 2 + 1);
tree[pos].tag = 0;
}
}
void update(int pos)
{
if (tree[pos].l >= x && tree[pos].r <= y)
{
addtag(pos);
return;
}
push_down(pos);
int mid = (tree[pos].l + tree[pos].r) / 2;
if (x <= mid)update(pos * 2);
if (y > mid)update(pos * 2 + 1);
push_up(pos);
}
long long query(int pos)
{
long long ans = 0;
if (tree[pos].l >= x && tree[pos].r <= y)
{
return tree[pos].value;
}
push_down(pos);
int mid = (tree[pos].l + tree[pos].r) / 2;
if (x <= mid)ans += query(pos * 2);
if (y > mid) ans += query(pos * 2 + 1);
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> ch[i];
bulit(1, 1, n);
while (m--)
{
int op;
cin >> op >> x >> y;
if (op == 1)
{
cin >> add;
update(1);
}
else cout << query(1) << endl;
}
return 0;
}
参考GPT和自己的思路:好的,你的问题是关于洛谷P3372线段树板子求调的,代码已经给出,想必你是遇到了一些问题。请问你具体有什么问题需要解答?