算法 c++ 数据结构 每日一题 第六十四期 洛谷 树状数组模板2

【模板】树状数组 2

题目描述

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

将某区间每一个数加上

x

x

x； 求出某一个数的值。

输入格式

第一行包含两个整数

N

N

N、

M

M

M，分别表示该数列数字的个数和操作的总个数。

第二行包含

N

N

N 个用空格分隔的整数，其中第

i

i

i 个数字表示数列第 $i $ 项的初始值。

接下来

M

M

M 行每行包含

2

2

2 或

4

4

4个整数，表示一个操作，具体如下：

操作

1

1

1： 格式：1 x y k 含义：将区间

[

x

,

y

]

[x,y]

[x,y] 内每个数加上

k

k

k；

操作

2

2

2： 格式：2 x 含义：输出第

x

x

x 个数的值。

输出格式

输出包含若干行整数，即为所有操作

2

2

2 的结果。

样例 #1

样例输入 #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\%

30% 的数据：

N

≤

8

N\le8

N≤8，

M

≤

10

M\le10

M≤10；

对于

70

%

70\%

70% 的数据：

N

≤

10000

N\le 10000

N≤10000，

M

≤

10000

M\le10000

M≤10000；

对于

100

%

100\%

100% 的数据：

1

≤

N

,

M

≤

500000

1 \leq N, M\le 500000

1≤N,M≤500000，

1

≤

x

,

y

≤

n

1 \leq x, y \leq n

1≤x,y≤n，保证任意时刻序列中任意元素的绝对值都不大于

2

30

2^{30}

230。

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define endl '\n'

//#define x first

//#define y second

using namespace std;

typedef long long ll;

typedef pairPII;

const int N=3e5+10;

const int MOD=1e9 + 7;

const int INF=0X3F3F3F3F;

const int dx[]={-1,1,0,0,-1,-1,+1,+1};

const int dy[]={0,0,-1,1,-1,+1,-1,+1};

const int M = 1e6 + 10;

int tree[M];//此时树状数组维护的是差分数组

int n, m;

int bit(int x)

{

return x & -x;

}

void add(int i, int x)

{

while(i <= n)

{

tree[i] += x;

i += bit(i);

}

}

int sum(int i)

{

int res = 0;

while(i > 0)

{

res += tree[i];

i -= bit(i);

}

return res;

}

int main()

{

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

cin >> n >> m;

for(int i = 1; i <= n; i ++)

{

int x;

cin >> x;

add(i, x);

add(i + 1, -x);

}

while(m --){

int a, x, y, k;

cin >> a;

if(a == 1)

{

cin >> x >> y >> k;

add(x, k);

add(y + 1, -k);

}

if(a == 2)

{

cin >> x;

cout << sum(x);

cout << endl;

}

}

return 0;

}

推荐文章