洛谷P3368 树状数组2

文章目录

洛谷P3368 树状数组2题目链接树状数组差分数组解决

题目链接

https://www.luogu.com.cn/problem/P3368

树状数组

学习树状数组：https://www.youtube.com/watch?v=v_wj_mOAlig。

首先简单介绍一下树状数组，以及为什么要使用树状数组。

假设有一个数组，我们需要对该数组执行如下操作（以下全部假设数组下标从1开始）：

求前i项的和。将第i项元素加上某个给定的值。

如果使用普通的数组，执行第一个操作的时间为$O(n)$，执行第二个操作的时间为$O(1)$。

如果用数组保存的内容为前缀和，执行第一个操作的时间为$O(1)$，执行第二个操作的时间为$O(n)$。

而使用树状数组，这两个操作的时间都为$O({\log }_{2}n)$。

关于树状数组的原理，请观看上面链接中的视频或寻找其他资料。

下面是C++的简单实现代码：

int n; int arr[500001]; inline int last_bit(int num) { return num & (-num); } // return the sum of [1, index] int sum(int index) { int res = 0; while (index) { res += arr[index]; index -= last_bit(index); } return res; } // plus value to the element of index of arr void add(int index, int value) { while (index <= n) { arr[index] += value; index += last_bit(index); } }

其中$arr$的第一个元素（下标为$0$）不使用，$n$为元素总数。

差分数组

假设有一个数组$arr1=[1,5,4,2,3]$，那么它的差分数组$arr2=[1,4,-1,-2,1]$。

即$arr2[i]=arr1[i]-arr1[i-1]$（其中$arr[0]$为$0$）。

可以发现$arr1[i]=arr2[1]+arr2[2]+arr2[3]+\cdots +arr2[i]$。例如$arr1[2]=arr2[1]+arr2[2]=1+4=5$。

即$arr1[i]$等于$arr2$的前$i$项和。

假设将区间$[2,4]$内所有数加$2$，那么$arr1$变为：$[1,7,6,4,3]$，而它的差分数组$arr2$为：$[1,6,-1,-2,-1]$。

可以发现$arr2$只有第$2$个和第$5$个元素的值改变了。

即$arr[2]=arr[2]+2$，$arr[4+1]=arr[4+1]-2$。

解决

因此，我们只需要在树状数组中维护一个差分数组，就能解决这个问题。

下面是C++的代码：

#include <iostream> int n, m; int arr[500001]; inline int last_bit(int num) { return num & (-num); } // return the sum of [1, index] int sum(int index) { int res = 0; while (index) { res += arr[index]; index -= last_bit(index); } return res; } // plus value to the element of index of arr void add(int index, int value) { while (index <= n) { arr[index] += value; index += last_bit(index); } } int main() { std::ios_base::sync_with_stdio(false); std::cin >> n >> m; int value, last_value = 0; for (int i = 1; i <= n; i++) { std::cin >> value; add(i, value - last_value); last_value = value; } int op; int x, y, k; for (int i = 0; i != m; i++) { std::cin >> op; switch (op) { case 1: std::cin >> x >> y >> k; add(x, k); add(y + 1, -k); break; case 2: std::cin >> x; std::cout << sum(x) << "\n"; break; default: break; } } }