ST（Spare Table稀疏表）

只看该作者 · 2023-4-21 23:28

ST（Spare Table稀疏表）算法采用了倍增思想，在O（nlogn）时间构造一个二维表，可以在O（1）时间在线查询[l,r]区间的最值，有效解决在校RMQ（Range Minimum/Maximum Query,区间最值查询）问题。
如何实现呢？
设F[i,j]表示[i,2j -1]区间的最值，区间长度为2j 。

根据倍增思想，长度为2j 的区间可分成两个长度为2j-1 的子区间的最值即可。递推公式：F[i,j]=max(F[i,j-1],F[i+2j-1 ,j-1])。

通过上面的讲解其实就是动态规划思想。

只看该作者 · 2023-4-21 23:28

1、ST创建
若F[i,j]表示[i,i+2j -1]区间的最值，区间长度为2j ,则i和j的取值范围是多少呢？
若数组的长度为n，最大区间长度2k ≤n<2k+1 ,则k=log2 n 向下取整，比如n=8时k=3，n=10时k=3.
在程序中，k=log2（n），也可用通用表达方式k=log（n）/log(2),log()表示以e为底的自然对数。

算法代码：

复制

void ST_create(){

for(int i=1;i<=n;i++)

        F[i][0]=a[i];//表示[i,i]区间的最值，区间长度为2^0

int k=log2(n);

for(int j=1;j<=k;j++)

        for(int i=1;i<=n-(1<<j)+1;i++)//n-2^j+1

                F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);

//j用来控制区间大小

}

只看该作者 · 2023-4-21 23:29

例如有10个元素a[1…10]={5,3,7,2,12,1,6,4,8,15}，其查询最值的ST如下图所示。

F[i，j]表示[i，i+2j-1] 区间的最值，区间长度为2j

只看该作者 · 2023-4-21 23:29

2、ST查询
若查询[l,r]区间的最值，则首先计算k的值，和前面的计算方法相同，区间长度为r-l+1,2k ≤r-l+1<2k+1 ,因此k=log2（r-l+1）。
若查询区间长度为大于等于2k且小于2k+1 ,则根据倍增思想，可以将查询区间分为两个查询区间，取两个区间的最值即可。两个区间分别从l向后的2k 个数及从r向前2k 个数。

只看该作者 · 2023-4-21 23:29

算法代码：

复制

int ST_query(int l,int r）

{

        int k=lng2(r-l+1);

        return max(F[l][k],F[r-(1<<2)+1][k]);

}

只看该作者 · 2024-6-6 07:01

在掌握对象的变化频度时是有效的

只看该作者 · 2024-6-6 08:04

中断信号直接从各外部设备通知中断控制器

只看该作者 · 2024-6-6 09:07

待向GPIO（通用I/O端口）的输入从0变为1时，程序可以一定的间隔来检查GPIO的状态

只看该作者 · 2024-6-6 11:03

来自单片机内部的定时器和GPIO、串行通信设备UART等外设机器的中断被称为外部设备中断

只看该作者 · 2024-6-6 12:06

定时器输出引脚的设定

只看该作者 · 2024-6-6 14:02

中断产生于单片机内部和外部的各种设备

只看该作者 · 2024-6-6 15:05

这样的设定只需在setup（）中定义一次便能在整个程序中有效

只看该作者 · 2024-6-6 17:01

多次检查也会给单片机带来负荷，对功耗不利

只看该作者 · 2024-6-6 18:04

在GR-SAKURA中，从IO30引脚到IO35引脚接收来自外部的中断信号

只看该作者 · 2024-6-6 19:07

一种了解状态变化的简单方法