P3368 【模板】树状数组 2

题目链接

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  1. 将某区间每一个数数加上 x
  2. 求出某一个数的值。

输入格式

第一行包含两个整数 NM(1N,M5×105),分别表示该数列数字的个数和操作的总个数。

第二行包含 N 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值。

接下来 M 行每行包含 24 个整数,表示一个操作,具体如下:

操作 1: 格式:1 x y k 含义:将区间 [x,y] 内每个数加上 k

操作 2: 格式:2 x 含义:输出第 x 个数的值。

输出格式

输出包含若干行整数,即为所有操作 2 的结果。

题解

树状数组区间修改单点查询模板题,暂无

代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int t[N], x, y, k, op, n, m;
void add(int x, int k) {
for (; x <= n; x += x & -x) t[x] += k;
}
int ask(int x) {
int res(0);
for (; x; x -= x & -x) res += t[x];
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> x, add(i, x - y), y = x;
for (int i = 1; i <= m; i++) {
cin >> op;
if (op == 1)
cin >> x >> y >> k, add(x, k), add(y + 1, -k);
else
cin >> x, cout << ask(x) << '\n';
}
return 0;
}

注意

  1. 差分查询插入时要注意
文章作者: answerend42
文章链接: http://answerend42.github.io/2020/11/12/lg3368/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog
Powered By Valine
v1.5.2