社区讨论

如何使用树状数组维护区间最值

学术版参与者 11已保存回复 32

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
31 条
当前快照
1 份
快照标识符
@m2kgbn4q
此快照首次捕获于
2024/10/22 20:58
去年
此快照最后确认于
2025/11/05 01:38
4 个月前
查看原帖
RT。只会维护区间和和区间修改,怎么维护区间最值。代码如下
CPP
struct BIT
{
    int c[2][N];
	int lowbit(int x){return x & -x;}
	void _add(int k, int x, int y) 
	{
		for (; x < N; x += lowbit(x)) 
		    c[k][x] += y;
	}
	int _ask(int k, int x) 
	{
		int res = 0;
		for (; x; x -= lowbit(x)) 
		    res += c[k][x];
		return res;
	}
	void add(int l, int r, int k)
	{
		_add(0, l, k), _add(0, r + 1, -k);
		_add(1, l, l * k), _add(1, r + 1, -(r + 1) * k);	
	}
	int ask(int x)
	{
		return (x + 1) * _ask(0, x) - _ask(1, x);
	}	
	int query(int l, int r)
	{
		return ((r + 1) * _ask(0, r + 1) - _ask(1, r + 1)) - (l * _ask(0, l) - _ask(1, l));
	}
} tree;

回复

32 条回复,欢迎继续交流。

正在加载回复...