P3368 【模板】树状数组 2

Posted Thu Mar 26 2020. 1031 words. 5 min read.
Cover Image

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

题目描述

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

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

输入格式

第一行包含两个整数 NNMM,分别表示该数列数字的个数和操作的总个数。

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

接下来 MM行每行包含 2 或 4 个整数,表示一个操作,具体如下:

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

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

输出格式

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

输入输出样例

输入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出 #1

6
10

说明/提示

样例 1 解释:

故输出结果为 6、10。


数据规模与约定

对于 30%30\% 的数据:N8,M10N\le8,M\le10

对于 70%70\% 的数据:N10000,M10000N\le 10000,M\le10000

对于 100%100\% 的数据:1N,M5000001 \leq N, M\le 5000001x,yn1 \leq x, y \leq n,保证任意时刻序列中任意元素的绝对值都不大于 2302^{30}

题解

上一篇文章已经讲了树状数组 1,单点修改区间查询。树状数组 1 文章链接

树状数组 2 需要实现的是区间修改,单点查询。

并且树状数组 2 要完全依赖于树状数组 1,仅在 1 的基础上引入差分数组

通过差分数组将其转换为单点修改区间查询,没错,就是树状数组 1,的单点修改区间查询

说到差分我就想到了 xzt 卖煎饼,想到 xzt 卖煎饼我就想到了暴力 O(nm)O(nm) 解法,想到这个解法就想到了我是多么菜鸡

前置知识 差分数组

现有一序列 AA

A=3,1,4,1,5,9,2,6,5A={3,\,1,\,4,\,1,\,5,\,9,\,2,\,6,\,5}

建立一个差分数组 DD,使得 Di=AiAi1D_i=A_i-A_{i-1}

D=3,  2,3,3,4,4,7,4,1D={3,\;-2,\,3,\,-3,\,4,\,4,\,-7,\,4,\,-1}

此时将 AA 序列中 A3A5A_3 \sim A_5 都加上 3,得到新的 AA

A=3,1,7,4,8,9,2,6,5A={3,\,1,\,7,\,4,\,8,\,9,\,2,\,6,\,5}

此时再更新 DD 数组

D=3,2,6,3,4,1,7,4,1D={3,\,-2,\,6,\,-3,\,4,\,1,\,-7,\,4,\,-1}

不难发现,在 AA 序列的 AiAjA_i \sim A_j 区间分别加上 nn ,在差分数组 DD 中就相当于 Di  +=  n,  Dj+1  =  nD_i\;+=\; n,\;D_{j+1}\;-=\;n

相信聪明的你已经发现了,这里出现了树状数组 1的单点修改

查询

这个也就变的很简单了,利用差分数组的性质,假设我们要求 A3A_3

那么

A3=D1+D2+D3A_3=D_1+D_2+D_3

好啦,就是这么简单

结束

附上 AC 代码

#include <cstdio>

int n,m,k,x,aa,l,r;
int a[500110],c[500110];

int read() {
bool flag = 1;
int x = 0;
char ch = getchar();
while (ch<'0' || ch>'9') {if (ch == '-') flag = 0; ch = getchar();}
while (ch>='0' && ch<='9') {x *= 10;x += ch-'0';ch=getchar();}
return flag ? x:-x;
}
int lowbit(int x) {
return x & -x;
}
void add(int x,int k) {
while (x<=n) {
c[x] += k;
x += lowbit(x);
}
}
int find(int x) {
int sum = 0;
while (x) {
sum += c[x];
x -= lowbit(x);
}
return sum;
}

int main() {
n = read(); m = read();
for (int i=1; i<=n; i++) {
a[i] = read();
add(i, a[i]-a[i-1]);
}
while (m--) {
aa = read();
if (aa==1) {
l = read(); r = read(); k =read();
add(l,k);
add(r+1,-k);
}
else {
k = read();
printf("%d\n", find(k));
}
}
return 0;
}


Comments

Unable to load Disqus, please make sure your network can access.