【题解】LuoGu1438：无聊的数列

最新推荐文章于 2024-05-28 13:13:13 发布

丰川样子小孩姐

最新推荐文章于 2024-05-28 13:13:13 发布

阅读量213

点赞数 1

分类专栏：题解树状数组差分文章标签：题解 LuoGu 树状数组差分

本文链接：https://blog.csdn.net/ModestCoder_/article/details/108477543

版权

题解同时被 3 个专栏收录

435 篇文章

订阅专栏

树状数组

28 篇文章

订阅专栏

差分

10 篇文章

订阅专栏

本文介绍了一种使用树状数组优化区间加等差数列和单点求和的问题解决方法。通过维护两个树状数组，分别记录和与增量，实现了对区间加等差数列的高效更新和查询，大幅减少了时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
区间加等差数列，单点求和，可以用树状数组维护
开两个树状数组，第一个维护和，第二个维护 $d e l t a$
魔改暴力加等差数列的方式，用树状数组只加 $l o g n$ 个地方，但我需要保存 $d e l t a$ ，求和的时候，累计和与 $k * d e l t a$ ，这个 $k$ 就是实际意义上的要求的第 $x$ 个数和当前的差

懂了具体操作之后，就知道如何更新了
$u p d a t e (l, k, d), u p d a t e (r + 1, - k - (r - l + 1) * d, - d)$

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, m, a[maxn], tree[maxn][2];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int lowbit(int x){ return x & -x; }
void update(int x, int k, int d){ for (; x <= n; x += lowbit(x)) tree[x][0] += k, tree[x][1] += d, k += d * lowbit(x); }
int query(int x){ int s = 0, p = x; for (; x; x -= lowbit(x)) s += tree[x][0] + (p - x) * tree[x][1]; return s; }

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