社区讨论
如何使用树状数组维护区间最值
学术版参与者 11已保存回复 32
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 31 条
- 当前快照
- 1 份
- 快照标识符
- @m2kgbn4q
- 此快照首次捕获于
- 2024/10/22 20:58 去年
- 此快照最后确认于
- 2025/11/05 01:38 4 个月前
RT。只会维护区间和和区间修改,怎么维护区间最值。代码如下
CPPstruct 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 条回复,欢迎继续交流。
正在加载回复...