L - 树状数组 2

 洛谷 - P3368 

Description

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

1. 将某区间每一个数加上 x；

2. 求出某一个数的值。

Input

第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。

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

接下来 M 行每行包含 2 或 4个整数，表示一个操作，具体如下：

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

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

Output

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

Sample 1

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

6
10

Hint

样例 1 解释：

故输出结果为 6、10。

数据规模与约定

对于 30%的数据：N≤8，M≤10；

对于 70%的数据：N≤10000，M≤10000；

对于 100% 的数据：1≤N,M≤500000，1≤x,y≤n，保证任意时刻序列中任意元素的绝对值都不大于 230。

思路：

问题分析

需要处理两种操作：

1. 区间增量操作：给区间[x, y]内的每个元素加上k。
2. 单点查询操作：查询第x个元素的值。

直接使用暴力方法（遍历区间进行增量）的时间复杂度为O(N)，对于大规模数据（如N=500000）会导致超时。因此需要使用更高效的数据结构或算法。

差分数组与树状数组优化

差分数组可以有效处理区间增量操作，树状数组（Fenwick Tree）可以高效实现差分数组的前缀和查询。

差分数组原理：

• 原数组A的差分数组D定义为D[1] = A[1]，D[i] = A[i] - A[i-1]（i > 1）。
• 区间增量操作[x, y]加上k，只需执行D[x] += k和D[y+1] -= k。
• 查询A[x]的值即为差分数组D的前缀和sum(D[1..x])。

树状数组优化：

• 树状数组支持高效的单点更新和前缀查询（O(logN)时间复杂度）。
• 用树状数组维护差分数组D，可以快速处理区间增量和单点查询。

代码实现思路

1. 初始化差分数组：

   • 读取初始数组并构建差分数组D，D[i] = A[i] - A[i-1]（i > 1），D[1] = A[1]。
   • 使用树状数组维护D的数值。

2. 处理操作：

   • 区间增量操作1 x y k：调用add(x, k)和add(y+1, -k)。
   • 单点查询操作2 x：调用count(x)获取前缀和，即A[x]的值。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[500005];
int lowbit(int x) {return x & (-x);
}
void add(int i, int w) {while (i <= n) {a[i] += w;i += lowbit(i);}
}
可以不写add中-w就OK了
//void sub(int i, int w) {
//    while (i <= n) {
//        a[i] -= w;
//        i += lowbit(i);
//    }
//}
int count(int i) {int result = 0;while (i > 0) {result += a[i];i -= lowbit(i);}return result;
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> m;int w;int u;for (int i = 1; i <= n; i++) {cin >> w;if (i == 1) {u = w;add(i, u);}elseadd(i, w-u);u = w;}int h, x,y, k;for (int i = 1; i <= m; i++) {cin >> h;if (h == 1) {cin >> x >> y >> k;add(x, k);add(y + 1, -k);}else {cin >> x;cout << count(x) << endl;}}return 0;
}