ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

树状数组维护区间最值

2023年3月10日 58点热度 0人点赞 0条评论

说起区间最值,容易想到ST表(动态规划写法),但是这种方法不能动态维护,只能维护一个固定的数组。再容易想到线段树,但是线段树的常数极大,每次写线段树都心惊胆战,就怕t了。

这篇文章介绍一下树状数组来维护区间最值。

回顾一下树状数组

说起树状数组,容易想到树状数组可以动态维护区间和,可以实现区间修改和区间查询。

它大概长这样:

图片源自 算法学习笔记(2) : 树状数组 - 知乎 (zhihu.com)

对于一个节点k,他的管辖区间为[k - lowbit(k) + 1, k],其本身作为右端点。

对于lowbit的解释:

lowbit(x) = x & -x

其数学含义是取出数字x的二进制表示中的从右往左第一个1,然后截断,例如lowbit(1011000)=(1000)

树状数组维护区间最值

树状数组维护的区间最值仅支持单点修改和区间查询。

值得注意的是,维护一个最值树状数组需要同时维护两个数组,分别是t(树状数组)和a(原数组)。

单点修改:复杂度O((logn)^2)

void update(int k, int x)//维护区间最大值,最小值只需要改max为min即可
{
	a[k] = x;
	while(k < maxn)
	{
		t[k] = x;
		for(int i = 1;i < lowbit(k); i <<= 1)
		{
			t[k] = max(t[k], t[k - i]);
		}
		k += lowbit(k);
	}
}

区间查询:复杂度O((logn)^2)

int queMax(int l, int r)
{
	int res = a[r];
	while(r >= l)
	{
		for(;r - lowbit(r) >= l; r -= lowbit(r))
		{
			res = max(res, t[r]);
		}
		res = max(res, a[r --]);
	}
	return res;
}

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: acm icpc rmq st表 动态维护区间最值 区间最值 树状数组
最后更新:2023年3月20日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 回顾一下树状数组
  • 树状数组维护区间最值

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号