2023年3月

前言

由于腾讯广点通的文档写的实在是太烂,坑点很多,而且老旧版本的API文档互相掺杂,客服响应缓慢(基本上不懂技术),一个简单的东西往往要浪费技术人员很长时间,特此写一篇博客,希望给正在对接这块的技术人员一些帮助,正值心情烦躁,略带情绪,吐槽勿怪
image

环境角色

  • 需求方
  • 广告代理商
  • 广点通

需求方委托广告代理商进行广告投放,因为我们主要是为了推广微信小程序,所以选择的广告平台为腾讯广点通,广告代理商根据需求做好广告素材,进行投放,需求方需要将广告产生的数据上报给广点通,广告代理商根据上报的数据结果,对广告投放进行优化,以达到最优的转化

开始接入

官方文档对一些关键词做了说明,以及上报接口的调用示例,但是对于不熟悉广告业务的开发者来说,是无法将整个流程串联起来的,就会导致数据上报成功了,但是后台却看不到数据

  • 2.个人理解,流程图
    image

  • 3.参数补充说明

__CLICK_ID__
__CLICK_TIME__
__ACCOUNT_ID__
__CALLBACK__
__QZ_GDT__
__GDT_VID__

按照旧版的文档以及我个人的理解,这类参数被称为宏,用作参数站位符,通过点击广告跳转到落地页,落地页上会带上这些参数,可以参考坑爹的文档

https://docs.qq.com/pdf/DQm1PUWRHZVdudkRG

监测接口地址,是根本就不会用到的东西,会对研发人员造成极大的干扰,所以不用配置,我们只用配置落地页地址,如下

pages/index/index?click_id=__CLICK_ID__&click_time=__CLICK_TIME__&account_id=__ACCOUNT_ID__&callback=__CALLBACK__&qz_gdt=__QZ_GDT__&gdt_vid=__GDT_VID__

配置好落地页,广告-在线预览里,可以配置预览的微信号,这些微信号可以在投放的渠道(朋友圈...)里刷到这条测试广告,但是通过这个方式产生的数据回传成功,不会显示,真TMD服了,那后台弄这个功能,有个JB用? 这里重点吐槽一下腾讯的客服的响应速度,无用消息居多

image

上报流程

  • 1.从落地页的url上,获取到需要的参数,比如click_id,如没有获取到,则为自然流量
  • 2.用户触发行为(注册,下单...)的时候,将获取的参数,一并传递给后端
  • 3.用户完成行为(注册,下单...)的时候,生成上报数据,并上报(建议使用异步,或者消息队列)
  • 4.强烈建议使用文档上的post方式上报,网上有人说get上报存在问题

复原IP地址

力扣题目链接(opens new window)

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

例如:"0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1:

  • 输入:s = "25525566666635"
  • 输出:["255.255.11.135","255.255.666666.35"]

示例 2:

  • 输入:s = "0000"
  • 输出:["0.0.0.0"]

示例 3:

  • 输入:s = "6666661"
  • 输出:["1.1.1.1"]

示例 4:

  • 输入:s = "010010"
  • 输出:["0.10.0.10","0.100.1.0"]

示例 5:

  • 输入:s = "101023"
  • 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 0 <= s.length <= 3000
  • s 仅由数字组成

思路

实际上还是分割问题,但是又多了一些条件

本题的麻烦的点在于有很多边界条件需要处理

待解决的问题有:

1、如何加入分割点

2、如何判断分割的段落是否为合法IP

插入分割点

"分割"这个动作与
分割回文串
里定义的一致,都是用beginIndex指到分割位置

不同的是,这里我们beginIndex指到分割的位置时,我们需要在这个位置
的后一位
插入分割点

(后面细说)

合法IP判断

这里我们需要写一个判断函数来判断IP 是否合法,函数的输入是
字符串

待判断的区间

bool isVaild(string& s, int start, int end){
    
}

这里本质上我们还是在s上操作,只是指定了操作的位置

首先需要明确非法IP的情况:

​ 0、所给的判断区间不合法

​ 1、以0开头的数字,例如:192 . 031 . 2 . 1

​ 2、负数

​ 3、IP段数值大于255

bool isVaild(string& s, int start, int end){
    if(start > end) return false;//所给的判断区间不合法
    
    //是否以0开头
    if(s[start] == '0' && start != end) return false;
    
    int num4IP = 0;
    for(int i = start; i < end; ++i){
        //是否为正数
        if(s[i] < 0 && s[i] > 9) return false;
        
        //IP段数值是否大于255
        num4IP = num4IP * 10 + (s[i] - '0');
        if(num4IP > 255) return false;        
    }
    return true;
}

这里有几个
关键点

1、判断是否有IP段以0开头

请注意,我们这里判断的是false的情况,也就是有IP段使用了0开头

判断条件除了直接看开头字符是否为0(
s[start] == '0'
)以外,还需要确保当前IP段的数字不是第一个获取到的,因此需要追加条件
start != end

什么意思呢?这里又涉及到单层处理中的逻辑

在单层处理时,我们会去遍历由beginIndex控制的s中的区间,每次遍历都会触发isVaild函数来判断当前遍历所得的IP段是否合法

isVaild函数需要输入一个判断区间(这个区间其实就是
[beginIndex, i]


第一次
遍历的时候,输入isVaild的区间是
[0, 0]
,此时会出现一种
特殊情况

例如,我们的数字字符串是:s = "0000"

那么
第一次
遍历获取IP段时,我们得到的是'0',从我们的角度来看,这种情况应该是合法的

如果我们不追加条件去判断当前遍历是不是第一次遍历,那么上述情况会被程序视为非法,就会导致错误

为什么
start != end
可以判断遍历是否为第一次遍历?

前面也说过了,因为我们输入的区间实际上是[beginIndex, i],那么这个区间只有在第一次遍历时才会出现左右边界相等的情况,即[0, 0]

2、判断IP段数值大于255

这里容易犯的一个错误是直接拿
s[i]
来和255进行大小判断

拜托,
s[i]
是什么?它是组成当前IP段的数字之一,单个数字怎么可能大于255,这样判断只会通过所有的情况

因此,这里需要一点小小的计算,我来模拟一下这个过程

	int num4IP = 0;
    for(int i = start; i < end; ++i){
        //是否为正数
        if(s[i] < 0 && s[i] > 9) return false;
        
        //IP段数值是否大于255
        num4IP = num4IP * 10 + (s[i] - '0');
        if(num4IP > 255) return false;        
    }

例如当前的IP段是164,

第一轮遍历拿到s[i]是1,此时num = 0 * 10 + ('2' - '0') = 1

第二轮遍历拿到s[i]是6,此时num = 1 * 10 + ('5' - '0') = 16

第三轮遍历拿到s[i]是4,此时num = 16 * 10 + ('4' - '0') = 164

164显然是满足条件的

发现没有,
num = num * 10 + (s[i] - '0');
的作用就是
把数据类型为字符串的IP段转化为整型,然后再判断

代码分析

开始写,还是老一套,回溯三部曲

1、确定回溯函数的参数和返回值

本题中我们是直接操作的数字字符串s,因此不需要返回值

输入参数是数字字符串s、beginIndex和countPoint

countPoint用于统计目前一共插入了几个分割点,用于终止判定

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数:数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){        
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

2、确定终止条件

这里就用到countPoint了

参考IP的结构,当我们已经插入了3个分割点时,这时需要结束了(不论之后还剩什么)

同时,我们还要判断一下被分割出来的第四段是否合法,合法就把当前插好的数字字符串s保存到结果数组(一定记得我们是对s进行操作,最后的结果也是处理好的s)

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数:数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

3、确定单层处理逻辑

在单层递归中,我们需要遍历由beginIndex控制的当前区间

使用for循环不断获取IP段,然后判断其是否合法

合法就在
当前位置 i 的后一个位置
插入分割点

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        ...
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数:数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        //确定终止条件
        //当分割点的数量达到3个时说明分割结束,此时字符串已经被分成4段
        //在这里还需要验证最后一段是否合法
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
        //确定单层处理逻辑
        for(int i = beginIndex; i < s.size(); ++i){
            //这里beginIndex不是固定的,下一层递归时beginIndex会由上一层递归传入
            if(isVaild(s, beginIndex, i)){                
                s.insert(s.begin() + i + 1, '.');//插入分割点
                countPoint++;//计数++
                backtracking(s, i + 2, countPoint);//只加1的话就到分割点的位置,所以得多加一个
                countPoint--;//回溯
                s.erase(s.begin() + i + 1);
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {        
    }
};

这里又涉及到一个边缘处理问题:插入分割点的位置

题外话:insert函数

本题中使用insert来在s中插入分割点

举个例子说明insert的使用:

teststr = "1234";
teststr.insert(1, '.');//在原串下标为1的字符1前插入'.'->"1.234"

所以为什么插分割点的时候的位置是
s.begin() + i + 1

因为
s.begin() + i
只定位到了当前指针 i 遍历到的位置,而我们希望在该位置之后加点,所以要再加1

例如遍历"1234",遍历时 i 指向2时,即下标2,我们需要在2后面打点,此时要输入insert的应该是下标3而不是下标2

完整代码

本题思路很清晰,但是难点在于有很多的边界条件

一旦处理不好或者忘了,就会出错

class Solution {
private:
    bool isVaild(string& s, int start, int end){
        //判断区间是否合法
        if(start > end) return false;
        //判断数字开头是否为0,为0非法
        if(s[start] == '0' && start != end){
            return false;
        }
        int num4IP = 0;
        //遍历待判断区间
        for(int i = start; i <= end; ++i){
            //是否为正数
            if(s[i] > '9' || s[i] < '0'){
                return false;
            }
            //是否在255范围内
            num4IP = num4IP * 10 + (s[i] - '0');
            if(num4IP > 255){
                return false;
            }
        }
        return true;
    }
    vector<string> res;
    //确定回溯函数的参数和返回值
    //参数:数字字符串、beginIndex、分割点计数变量
    void backtracking(string& s, int beginIndex, int countPoint){
        //确定终止条件
        //当分割点的数量达到3个时说明分割结束,此时字符串已经被分成4段
        //在这里还需要验证最后一段是否合法
        if(countPoint == 3){
            if(isVaild(s, beginIndex, s.size() - 1)){//判断第四段是否合法
                res.push_back(s);                
            }
            return;
        }
        //确定单层处理逻辑
        for(int i = beginIndex; i < s.size(); ++i){
            //这里beginIndex不是固定的,下一层递归时beginIndex会由上一层递归传入
            if(isVaild(s, beginIndex, i)){                
                s.insert(s.begin() + i + 1, '.');//插入分割点
                countPoint++;//计数++
                backtracking(s, i + 2, countPoint);//只加1的话就到分割点的位置,所以得多加一个
                countPoint--;//回溯
                s.erase(s.begin() + i + 1);
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        //这里可以先判断一下字符串s是否合法
        if(s.size() < 4 || s.size() > 12) return res;
        backtracking(s, 0, 0);
        return res;
    }
};

本书把所构想的语言机器作为语言媒介系统工具的最新发展,语言机器也可以放在计算机器的历史中来进行分析与比较。

图灵在构想图灵机时,是从观察人用笔在纸上进行计算的过程开始的,所构想的图灵机装置就是用来模拟人类计算过程中的行为。图灵机通过建立符号,内部状态,以及输入与状态如何决定输出的规则来对计算问题建模。简单地说,给出输入,图灵机就能有规则地输出。图灵机的思想更多是从机器出发的,这体现于图灵机的原子操作都是基于一个字符进行的:读入一个字符,进行判断处理,输出也只是一个字符或无输出。这从人的视角来理解并不自然。人工计算操作时关注对象是各种表达式,只在特定的情形下,才可能是单个的符号。在本书中,我们把计算看作是表达式上的等价-替换作为计算操作。在抽象的意义上,图灵机从输入到规则的输出也可看作是一种替换操作。只是单个符号上的替换并不是人类计算行为模式。带来的效果是同样的问题通常图灵机需要建立更多的规则。

前面讲过,图灵机与乔姆斯基的2型文法等价。乔姆斯基文法理论的基础,如产生式规则,性质上也是一种替换操作。乔姆斯基的文法理论构成了现代程序设计语言的语法基础。在图灵提交其论文几个月前,美国数学家阿隆佐·邱奇(Alonzo Church:1903.6–1995.8)提交了论文“关于判定性问题的解释”,同样证明了判定性问题无解。邱奇的论证基于Lambda演算。邱奇的Lambda演算与图灵机的计算能力等价。考察Lambda演算理论,可以发现演算所进行的操作,明显地体现为递归的符号替换。对计算机器历史进行更多考察,可发现其它基于类似替换操作设计的计算机器模型。图灵机思想里没有说明从输入到输出的规则从那里来,这看作是开放的。邱奇Lambda演算理论、乔姆斯基文法理论及其他的理论与模型,也都是从特定技术角度来考虑替换的。本书里并不把计算作为一个独立的主题来研究,而是把计算放在符号使用的背景下来研究,计算所依据的替换规则可归为知识或事实里的等价关系,包括现有的等价关系,以及潜在可推导出的等价关系。本书所基于的背景,使得机器可以作为语言媒介系统的工具。

现代计算机是图灵机的一种工程实现,图灵机并不是只能以现代计算机这样的方式实现。现代计算机的处理最终都分解回算术、逻辑的计算,图灵机理论本身没有这样的要求,这只是技术路线决定的。二进制及其计算在符号与物理上的一致性带来了现代的计算机。在语言机器构想中,从计算执行的效率来说,基于替换-转换的过程可以具有特别的优势。因为这可以在任何层次的表达式上直接进行操作,减少了分解回到原子操作的过程。表达式上的一次替换-转换操作对应的是多次现代计算机的原子级的算术、逻辑计算操作及相应的内部通信,理论上空间与时间的消耗都会更小。

利用现在的计算机,虚拟出在表达式层次进行替换-转换操作的能力是可能的,或者封装出基于替换-转换操作的程序设计语言也是可能的。对语言机器的目标来说,这些方案只具有有限的验证意义。首先这带来了某种循环:基于逻辑、算术的计算去虚拟替换-转换操作,基于替换-转换操作又去构造逻辑、数学上的计算。概念上,本书认为替换-转换是比逻辑、算术计算更为基础的操作。其次,这牺牲了语言机器可能具有的效率优势。语言机器的构想,其设计与实现可能借鉴当前计算机的一些技术,整体的使用模式上很难去与冯·诺依曼型机器的使用类比。可以预计语言机器得以实现,它的能力也不会超过一台通用图灵机,这也不构成对语言机器的关键评价,语言机器所追求的是新的人机协同所能带来的效果,这些效果首先对人而言的。

如果语言机器最终是可实现的,这种机器是专用的,还是可以作为新的通用机器?现在去考虑这样的问题显得太早。可以看到,到目前本书的讨论基本是限定在理论性知识的范围,相比较,现在计算机的应用主要是在技术、工程性的领域。在这些领域的问题处理中,很多的问题并不是典型的计算问题;各类的问题的求解,经验性规则同样重要,它们不都是从理论可推导出的。本书是将语言机器放在语言工具的视角下来理解,支撑人对符号的使用始终是第一位。另一方面,机器一旦表现出某些潜力,人们就会去让机器的潜力得到最大的发挥,这种努力更容易进行,并可能对机器面向人的符号使用的目标产生反作用。

应用上,语言机器在语言机制与内容上的深入,与当前人工智能所考虑的问题相关,从而二者也可以去比较。根本上,它们思想上的出发点是不一样的。语言机器的首要目标是替换纸张、笔、墨水、计算机之类的工具来支撑人类的语言构建与使用,实现工具辅助下更有效的人类语言使用。当代的人工智能总的来说是用机器来模拟人脑的智力行为,从而更多原来由人完成的工作可以由机器替代。本书把人类的智力看作随符号使用而发挥或扩展的,而不是一个大致固定的模式可以用机器去模仿并替代。

在更好地配合人类使用符号的同时,人所具备的知识,机器可以以越来越相近的方式具备,且机器所具备的知识可以超出任何人类个体的容量;以前由人进行的符号规则性操作,越来越多可由机器执行,并且更具效率;此时,说机器表现出的行为具有智能的性质也没什么问题。我们来看一个具体的例子,类别与实例的关系。A是一个类别,x为类别下的一个实例,我们说x归属A,“归属”这个词可以通过解释为人理解。这种解释形成的理解是否真正有效是存疑的,我们也不可能对机器进行这样的解释。现在,可以实现这样的机制:x是类别A下的一个实例,包含A的任何命题,可以用x来替换其中的A,命题仍然成立。这种可替代的关系在特定语境中可由机器实际执行,从操作的意义上,语言机器表现出已理解了“x是类别A下的一个实例”。机器不会象人一样去理解符号单位有没有意义,具体有什么意义;另一方面,理解的一个重要标志是知道如何去操作符号。

一种流行的观点认为现代计算机较擅长处理结构化规则性知识,而对非结构化开放性的知识,如常识一类的知识,机器处理能力一般; 机器在后一方向上进展,可以更多理解与模仿出人类的智能。首先,本书不认为已建立了对结构化规则性知识的完善理解,并将这一理解体现在机器应用上。现代计算机是从将计算作为一个独立的主题开始的。为此,本书建立了自己的理论,核心的观点是:知识基于等价关系表示,计算依据等价关系进行。在此基础上,我们论述了知识如何在机器里建立,从而也使机器具备推演能力。重要的是那些结构化规则性的知识,对应着符号对人类智能与认知的扩展,从机器与人类分工的角度,改善或创新工具来增强这种扩展是一种合理的做法。

对常识的重视使自然语言也成为当前人工智能的一个核心主题。通过建立复杂的语言模型,在大量语料上进行统计计算,机器也表现出一定的语言处理能力。从经济角度,这些进展可以具有巨大的价值,绝大多数的白领工作都是一些固定模式的工作,并不需要真正的创造性。这些处理接近了人类智力的某些部分,这是有可能的,但这不会是核心的部分。语言机器所具有的推演能力,理想的情况下是从当前已知的理论与事实,可以计算出所有可能的结论,这种能力是人类借助符号扩展的那一部分智力,本书只是重新理解并去将这一部分的智力实现为更通用的方式。

当我们建立的系统表现出可以命名、可以定义、可以去形成新的认知并表达,以及能提出问题,大概才能说接近了人类智力的核心。这可能需要更系统的研究,建立从感知经验到符号系统,从自然语言到抽象符号系统的连续理解,才可能发现背后是否存在一些始终依赖的智力形式。本书更关心的是:能否发展新的符号形式与使用方式,使人类对符号的使用更高效。

目录

LVGL简介

嵌入式常用的图形显示库

对设备的要求是 "all you need is at least 32kB RAM and 128 kB Flash, a C compiler, a frame buffer, and at least an 1/10 screen sized buffer for rendering". 最低要求是128KB Flash, 但实际上这个大小基本上什么也做不了, 所以直接用256K Flash 的 AIR32F103CCT6 和 AIR32F103RPT6.

集成LVGL到AIR32F103

Principle 大佬写过一篇
Air32F103试玩-移植LVGL+FreeRTOS
Keil5 用户可以参考. 基于STM32标准库, 用的屏幕是 GC9306X 320x240LCD.

我没有这个型号的屏幕, 手里能找到现成的串口屏只有一个128x160的ST7735, 就用这个做测试吧.

基本步骤

参考LVGL的文档, 这两片内容差不多的, 第二篇会更细节一点

需要做的步骤为

  1. 将 lvgl 库目录放到项目里
  2. 复制一份 lvgl/lv_conf_template.h , 改名为 lv_conf.h 并修改定制
  3. 在项目中需要使用lvgl的地方, 包含 lvgl/lvgl.h 头文件
  4. 建一个定时器, 每隔1到10毫秒调用一次 lv_tick_inc(x) 用于lvgl内部定时. 如果不用这个方法, 就要定义 LV_TICK_CUSTOM 让 LVGL 可以直接读取时间.
  5. 调用 lv_init() 执行初始化
  6. 创建一个图像缓冲, 最小为1/10个屏幕尺寸所需要的数据大小.
  7. 实现一个绘图函数, 用于LVGL调用后往设备的指定区域写入显示内容.
  8. 如果有输入设备, 还可以再实现一个输入读取函数
  9. 在主循环 main while(1) 中, 如果是RTOS环境则在一个循环任务中, 每隔几个毫秒调用一次 lv_timer_handler(), 用于LVGL绘制更新图像显示.

最小化实现

1.将LVGL添加到项目中


https://github.com/lvgl/lvgl/releases
下载LVGL, 当前版本是v8.3.5, 解压.

在项目 Libraries 下创建lvgl目录, 复制必须的文件到这个目录下

demos/
examples/
src/
LICENCE.txt
lv_conf_template.h
lvgl.h
lvgl.mk

复制后的 Libraries 目录结构为

Libraries
├───AIR32F10xLib
├───CMSIS
├───Debug
├───DeviceSupport
├───EPaper
├───FreeRTOS
├───Helix
├───LDScripts
├───lvgl
│   ├───demos
│   ├───examples
│   └───src
│       ├───core
│       ├───draw
│       ├───extra
│       ├───font
│       ├───hal
│       ├───misc
│       └───widgets

在 Makefile 中添加 LVGL 选项

# Build with lvgl, y:yes, n:no
USE_LVGL		?= n

LVGL的编译列表和头文件路径都已经在 lvgl.mk 里定义好了, 这里只需要把它 include 进来, 再合并到项目的列表中.

ifeq ($(USE_LVGL),y)
LVGL_DIR	?= Libraries
LVGL_DIR_NAME	?= lvgl

include Libraries/lvgl/lvgl.mk

CFILES 		+= $(CSRCS)
INCLUDES	+= Libraries/lvgl

else

CFLAGS		?= 

endif

将 USE_LVGL 设为 y 之后, make 就会带上 LVGL 一起编译. 因为 LVGL 文件很多, 编译时间较长, 可以根据自己电脑的CPU个数设置并发编译, 例如对于8个逻辑核的L480, 可以执行

make -j8

因为编译结果有200多KByte, 写入的速度也很慢, 暂时没有什么好办法.

2. 定制 lv_conf.h

将 lvgl/lv_conf_template.h, 复制到 user 目录下, 改名为 lv_conf.h, 编辑


#if 0
改为
#if 1

/* clang-format off */
#if 1 /*Set it to "1" to enable content*/

因为ST7735支持的是2byte的像素, 色深设为 16

/*Color depth: 1 (1 byte per pixel), 8 (RGB332), 16 (RGB565), 32 (ARGB8888)*/
#define LV_COLOR_DEPTH 16

再往下, 都是用0和1代表对应功能项的关和开, 可以保持默认. 因为ST7735屏幕分辨率较小, 所以再修改一下字体, 将
LV_FONT_MONTSERRAT_10
改为1, 将
LV_FONT_MONTSERRAT_14
改为0 启用10像素字体

#define LV_FONT_MONTSERRAT_10 0
#define LV_FONT_MONTSERRAT_12 0
#define LV_FONT_MONTSERRAT_14 1

再设置一下
LV_FONT_DEFAULT
, 改为
&lv_font_montserrat_10
, 替换为刚才启用的 10像素字体

/*Always set a default font*/
#define LV_FONT_DEFAULT &lv_font_montserrat_14

3. 创建 lv_tick_inc(x) 定时器

这里使用TIM3, 将定时间隔设为1毫秒, 开启 TIM_IT_Update 中断

void TIM3_Configuration(void)
{
  TIM_TimeBaseInitTypeDef TIM_TimeBaseStructure;
  NVIC_InitTypeDef NVIC_InitStructure;

  RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM3, ENABLE);
  // Set counter limit to 100 -- interval will be 1ms
  TIM_TimeBaseStructure.TIM_Period = 100 - 1;
  /**
   * Clock source of TIM2,3,4,5,6,7: if(APB1 prescaler =1) then PCLK1 x1, else PCLK1 x2
   * */
  if (clocks.HCLK_Frequency == clocks.PCLK1_Frequency)
  {
    // clock source is PCLK1 x1.
    // Note: TIM_Prescaler is 16bit, [0, 65535], given PCLK1 is 36MHz, divider should > 550
    TIM_TimeBaseStructure.TIM_Prescaler = clocks.PCLK1_Frequency / 100000 - 1;
  }
  else
  {
    // clock source is PCLK1 x2
    TIM_TimeBaseStructure.TIM_Prescaler = clocks.PCLK1_Frequency * 2 / 100000 - 1;
  }
  TIM_TimeBaseStructure.TIM_ClockDivision = TIM_CKD_DIV1; // TDTS = Tck_tim
  TIM_TimeBaseStructure.TIM_CounterMode = TIM_CounterMode_Up;
  TIM_TimeBaseInit(TIM3, &TIM_TimeBaseStructure);
  // Enable interrupt from 'TIM update'
  TIM_ITConfig(TIM3, TIM_IT_Update, ENABLE);

  // NVIC config
  NVIC_InitStructure.NVIC_IRQChannel = TIM3_IRQn;
  NVIC_InitStructure.NVIC_IRQChannelPreemptionPriority = 0;
  NVIC_InitStructure.NVIC_IRQChannelSubPriority = 3;
  NVIC_InitStructure.NVIC_IRQChannelCmd = ENABLE;
  NVIC_Init(&NVIC_InitStructure);

  TIM_Cmd(TIM3, ENABLE);
}

创建TIM3的中断回调函数, 因为定时器间隔为1毫秒, 因此使用
lv_tick_inc(1)

void TIM3_IRQHandler(void)
{
  if (TIM_GetITStatus(TIM3, TIM_IT_Update) != RESET)
  {
    // Clear INT flag
    TIM_ClearITPendingBit(TIM3, TIM_IT_Update);
    // Required for the internal timing of LVGL
    lv_tick_inc(1);
  }
}

如果提示找不到 lv_tick_inc(), 需要加上对头文件 lvgl/lvgl.h 的 include

4. 创建绘图函数

这里涉及到三部分: 初始化 SPI 和对应的 GPIO, 初始化 ST7735, 最后才是 ST7735 的绘图函数.

初始化 GPIO, 这4个pin是需要声明为推挽输出的 PA2:BL, PA3:CS, PA4:DC(Data/Command), PA6:RESET


void APP_GPIO_Config(void)
{
  GPIO_InitTypeDef GPIO_InitStructure;

  RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE);

  GPIO_InitStructure.GPIO_Pin = GPIO_Pin_2 | GPIO_Pin_3 | GPIO_Pin_4 | GPIO_Pin_6;
  GPIO_InitStructure.GPIO_Mode = GPIO_Mode_Out_PP;
  GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;
  GPIO_Init(GPIOA, &GPIO_InitStructure);
  GPIO_SetBits(GPIOA, GPIO_Pin_2 | GPIO_Pin_3 | GPIO_Pin_4 | GPIO_Pin_6);
}

初始化 SPI, 这里还需要设置 PA5:SCK/SCL 和 PA7:SI/SDA

void APP_SPI_Config(void)
{
  GPIO_InitTypeDef GPIO_InitStructure;
  SPI_InitTypeDef  SPI_InitStructure;

  RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE);
  RCC_APB2PeriphClockCmd(RCC_APB2Periph_SPI1, ENABLE);

  GPIO_InitStructure.GPIO_Pin = GPIO_Pin_5 | GPIO_Pin_7;
  GPIO_InitStructure.GPIO_Mode = GPIO_Mode_AF_PP;
  GPIO_InitStructure.GPIO_Speed = GPIO_Speed_50MHz;
  GPIO_Init(GPIOA, &GPIO_InitStructure);

  GPIO_SetBits(GPIOA,GPIO_Pin_5 | GPIO_Pin_7);

  SPI_InitStructure.SPI_Direction = SPI_Direction_1Line_Tx;
  SPI_InitStructure.SPI_Mode = SPI_Mode_Master;
  SPI_InitStructure.SPI_DataSize = SPI_DataSize_8b;
  SPI_InitStructure.SPI_CPOL = SPI_CPOL_Low;
  SPI_InitStructure.SPI_CPHA = SPI_CPHA_1Edge;
  SPI_InitStructure.SPI_NSS = SPI_NSS_Soft;
  SPI_InitStructure.SPI_BaudRatePrescaler = SPI_BaudRatePrescaler_16;
  SPI_InitStructure.SPI_FirstBit = SPI_FirstBit_MSB;
  SPI_InitStructure.SPI_CRCPolynomial = 0;
  SPI_Init(SPI1, &SPI_InitStructure);

  SPI_Cmd(SPI1, ENABLE);
}

初始化 ST7735, 这部分已经在 st7735.c 中封装, 直接在main()中调用即可

ST7735_Init();

创建 ST7735 的区域绘图函数

void my_disp_flush(lv_disp_drv_t *disp, const lv_area_t *area, lv_color_t *color_p)
{
  ST7735_WriteAddrWindow(area->x1, area->y1, area->x2, area->y2, (uint16_t *)color_p);
  // Indicate you are ready with the flushing
  lv_disp_flush_ready(disp);
}

对应的 ST7735_WriteAddrWindow() 函数实现, 因为来源是16bit, SPI接口是8bit, 每一次调用分别写入两次

void ST7735_WriteAddrWindow(uint16_t x1, uint16_t y1, uint16_t x2, uint16_t y2, uint16_t *data)
{
  uint32_t tmp, i;
  if (x1 > x2)
  {
    tmp = x1; x1 = x2; x2 = tmp;
  }
  if (y1 > y2)
  {
    tmp = y1; y1 = y2; y2 = tmp;
  }
  tmp = (x2 - x1 + 1) * (y2 - y1 + 1);
  ST7735_CS_LOW;
  ST7735_SetAddrWindow(x1, y1, x2, y2);
  while (SPI_I2S_GetFlagStatus(SPI1, SPI_I2S_FLAG_TXE) == RESET);
  for(i = 0; i < tmp; i ++) 
  {
    SPI_I2S_SendData(SPI1, (uint8_t)(*data >> 8));
    while(SPI_I2S_GetFlagStatus(SPI1, SPI_I2S_FLAG_BSY) == SET);
    SPI_I2S_SendData(SPI1, (uint8_t)(*data & 0xFF));
    while(SPI_I2S_GetFlagStatus(SPI1, SPI_I2S_FLAG_BSY) == SET);
    data++;
  }
  ST7735_CS_HIGH;
}

5. 创建图像缓冲, 初始化LVGL

最小为1/10个屏幕尺寸所需数据大小

static lv_disp_draw_buf_t draw_buf;
// Declare a buffer for 1/10 screen size
static lv_color_t buf1[ST7735_WIDTH * ST7735_HEIGHT / 10];
// Descriptor of a display driver
static lv_disp_drv_t disp_drv;

在 main() 中进行初始化, 注意这部分官网给代码里的类型不太对, 这部分的代码已经修改

lv_init();
// Initialize the display buffer.
lv_disp_draw_buf_init(&draw_buf, buf1, NULL, ST7735_WIDTH * ST7735_HEIGHT / 10);

lv_disp_drv_init(&disp_drv);                /*Basic initialization*/
disp_drv.flush_cb = my_disp_flush;          /*Set your driver function*/
disp_drv.draw_buf = &draw_buf;              /*Assign the buffer to the display*/
disp_drv.hor_res = ST7735_WIDTH;            /*Set the horizontal resolution of the display*/
disp_drv.ver_res = ST7735_HEIGHT;           /*Set the vertical resolution of the display*/
lv_disp_drv_register(&disp_drv);            /*Finally register the driver*/

6. 主循环添加 lv_timer_handler()

因为这个 ST7735 没有触屏功能, 所以输入读取函数就省了. 在 main() while(1)主循环中加上 lv_timer_handler()

  while (1)
  {
    lv_timer_handler();
    Delay_Ms(10);
  }

6. 执行示例

经过以上的设置, LVGL就已经集成到项目中了, 可以运行LVGL自带的一些例子查看控件的显示效果

文字标签, 居中和滚动的效果

lv_example_label_1();

按钮效果

lv_example_btn_1();

源代码

以上LVGL整合示例的完整源代码已经提交到 GitHub:
https://github.com/IOsetting/air32f103-template/tree/master/Examples/NonFreeRTOS/SPI/ST7735_LVGL

修改为 DMA 输出

上面的例子是使用
SPI_I2S_SendData()
函数传输图像数据的, 可以修改为 DMA 传输, 因为传输方式的变化, 外设初始化和图像更新要做对应的调整, 这里没有使用中断.

1. 外设调整

GPIO 不变, 启用 SPI 的 DMA


APP_SPI_Config()
中启用SPI1 DMA

  /* Enable SPI1 DMA TX request */
  SPI_I2S_DMACmd(SPI1, SPI_I2S_DMAReq_Tx, ENABLE); 

开启 DMA 时钟

void APP_DMA_Configuration(void)
{
  RCC_AHBPeriphClockCmd(RCC_AHBPeriph_DMA1, ENABLE);
}

因为DMA每次传输的数量在变化, 所以DMA的初始化在图像输出的方法里

2. 修改图像更新方法

图像更新方法的变化比较大, 这里需要根据输入的坐标, 计算实际的数据长度, 并对DMA进行初始化, 然后启动传输, 等待完成后关闭DMA

void my_disp_flush(lv_disp_drv_t *disp, const lv_area_t *area, lv_color_t *color_p)
{
  uint16_t len;
  DMA_InitTypeDef initStructure;

  len = (area->x2 - area->x1 + 1) * (area->y2 - area->y1 + 1) * 2;

  ST7735_CS_LOW;
  ST7735_SetAddrWindow(area->x1, area->y1, area->x2, area->y2);
  /* DMA1 Channel3 (triggered by SPI1 Tx event) Config */
  DMA_DeInit(DMA1_Channel3);
  initStructure.DMA_BufferSize = len;
  initStructure.DMA_M2M = DMA_M2M_Disable;
  initStructure.DMA_DIR = DMA_DIR_PeripheralDST;
  initStructure.DMA_MemoryBaseAddr = (uint32_t)color_p;
  initStructure.DMA_MemoryDataSize = DMA_MemoryDataSize_Byte;
  initStructure.DMA_MemoryInc = DMA_MemoryInc_Enable;
  initStructure.DMA_PeripheralBaseAddr = (uint32_t)&SPI1->DR;
  initStructure.DMA_PeripheralDataSize = DMA_PeripheralDataSize_Byte;
  initStructure.DMA_PeripheralInc = DMA_PeripheralInc_Disable;
  initStructure.DMA_Priority = DMA_Priority_High;
  initStructure.DMA_Mode = DMA_Mode_Normal;
  DMA_Init(DMA1_Channel3, &initStructure);
  // Start transfer
  DMA_Cmd(DMA1_Channel3, ENABLE);
  while (!DMA_GetFlagStatus(DMA1_FLAG_TC3));
  DMA_ClearFlag(DMA1_FLAG_TC3);
  DMA_Cmd(DMA1_Channel3, DISABLE);
  ST7735_CS_HIGH;

  // Indicate you are ready with the flushing
  lv_disp_flush_ready(disp);
}

3. 修改色彩字节顺序

上面修改完成后, 再次运行LVGL示例, 会发现颜色不正确, 这是因为在DMA传输中, 将一个 16bit 强转为两个 8bit 了, ST7735收到的两个字节的顺序有变化, 需要编辑 lv_conf.h, 将
LV_COLOR_16_SWAP
设为
1

/*Swap the 2 bytes of RGB565 color. Useful if the display has an 8-bit interface (e.g. SPI)*/
#define LV_COLOR_16_SWAP 1

源代码

以上LVGL DMA 示例的完整源代码已经提交到 GitHub:
https://github.com/IOsetting/air32f103-template/tree/master/Examples/NonFreeRTOS/SPI/ST7735_LVGL_DMA

集成到 FreeRTOS

进一步, 在 FreeRTOS 中运行 DMA 传输的 LVGL. 在 FreeRTOS 中 LVGL 的初始化是一样的, 有变化的是初始化的时间点, 还有延时函数的修改

1. 将初始化从 main() 移入任务handler

新建
lvglTaskHandler()
用于处理LVGL初始化, 缓存初始化和执行benchmark, 并用固定间隔调用
lv_timer_handler()

static void lvglTaskHandler(void *pvParameters)
{
  TickType_t xLastWakeTime = xTaskGetTickCount();
  const TickType_t xPeriod = pdMS_TO_TICKS(10);
  (void)(pvParameters); // Suppress "unused parameter" warning

  ST7735_Init();

  lv_init();

  // Initialize the display buffer.
  lv_disp_draw_buf_init(&draw_buf, buf1, NULL, ST7735_WIDTH * ST7735_HEIGHT / 10);

  lv_disp_drv_init(&disp_drv);                /*Basic initialization*/
  disp_drv.flush_cb = my_disp_flush;          /*Set your driver function*/
  disp_drv.draw_buf = &draw_buf;              /*Assign the buffer to the display*/
  disp_drv.hor_res = ST7735_WIDTH;            /*Set the horizontal resolution of the display*/
  disp_drv.ver_res = ST7735_HEIGHT;           /*Set the vertical resolution of the display*/
  lv_disp_drv_register(&disp_drv);            /*Finally register the driver*/

  lv_demo_benchmark();

  while (1)
  {
    lv_timer_handler();
    vTaskDelayUntil(&xLastWakeTime, xPeriod);
  }
}

在 main() 中创建任务, 栈深度1024, 需要 4KByte 内存

xTaskCreate(
        lvglTaskHandler,              // Task function point
        "LVGL Task",                  // Task name
        1024,                         // Stack size, each take 4 bytes(32bit)
        NULL,                         // Parameters
        LVGL_TASK_PRORITY,            // Priority
        NULL);                        // Task handler

2. 修改延时函数

更新图像的方法不变, 但是需要修改 ST7735 的延时函数, 修改 st7735.c, 引入
FreeRTOS.h
, 将
Delay_Ms(ms);
替换为
vTaskDelay(ms);

3. 中断设置

在 FreeRTOSConfig.h 中, 设置系统最高的, 可以安全使用FreeRTOS方法的中断优先级为
1

#define configLIBRARY_MAX_SYSCALL_INTERRUPT_PRIORITY	0x01

因为 AIR32F103 的中断为 3 bit, 可用的优先级为 0 到 7, 这样对于优先级为 0 的中断是不受FreeRTOS控制的, 小于等于 1 的是受FreeRTOS控制的, 可以在中断处理中调用 FreeRTOS 的方法.

将TIM3的中断优先级设置为2

NVIC_InitStructure.NVIC_IRQChannel = TIM3_IRQn;
NVIC_InitStructure.NVIC_IRQChannelPreemptionPriority = 2;
NVIC_InitStructure.NVIC_IRQChannelSubPriority = 0;
NVIC_InitStructure.NVIC_IRQChannelCmd = ENABLE;
NVIC_Init(&NVIC_InitStructure);

4. 裁剪 LVGL

因为集成FreeRTOS, 加上运行 Benchmark, 256KB 的 Flash 容量就捉襟见肘了, 默认配置下编译出来会有300多KB, 需要进行压缩

首先确认编译参数已经优化, rules.mk 中, 优化项改为
-O3

-Os

# c flags
OPT			?= -O3

编辑 lv_conf.h 关闭一切不必要的组件, 使用尽可能小的字体(可以用10像素字体), 具体的改动可以参考示例代码.

源代码

以上LVGL+FreeRTO 示例的源代码已经提交到 GitHub:
https://github.com/IOsetting/air32f103-template/tree/master/Examples/FreeRTOS/LVGL/ST7735_128x160

最后

以上就是在 AIR32F103 上集成 LVGL 的步骤和说明, ST7735 也是常见模块. 对于 DMA 的例子, 可以进一步修改为使用中断判断 DMA 传输结束. 留有空再改了.

平衡树

建议在清楚二叉搜索树的所有操作之后食用本文。本文将略过部分基础知识

本文主要会讲到4中较常用的平衡树:

  • Treap

  • FHQ-Treap(无旋Treap)

  • Splay

  • WBLT

其实WBLT不怎么常用,但是我个人最喜欢用

我将会在另一篇文章中讲述其他的平衡树,如AVL,红黑树,替罪羊树等。

可持久化我还会放在另一篇文章中讲述,敬请期待。

Treap

Treap也就是
Tree + Heap
,在满足二叉搜索树的前提下,通过维护二叉堆的性质来保证其复杂度不会太大,一般我们认为是
\(O(\log n)\)
的单次操作复杂度。但是毕竟是随机的,还是可能会炸,此乃后话。

先声明一点名词:

  • 权值:也就是数据,每一个结点保存的数据。

  • 优先度:用于维护二叉堆性质,是新建结点的时候随机生成的。

图中我会以二元组的形式给出,格式为
权值,优先度

我一般习惯用大根堆,且优先度为非负数,这样要方便一点

这是一颗很简单的树,我们现在来考虑各种操作。

不过,我还是给出树的声明:

其他的树定义类似!

typedef unsigned int uint;
template<int N = 1e5 + 3>
class Treap {
private:
    int lc[N], rc[N]; // 左右节点
    uint pri[N]; // 优先度,定义为非负整数!
    int val[N]; // 权值
    int cnt[N]; // 计数器
    int siz[N]; // 以当前结点为根的子树的结点个数(用于查找kth和rank)
    int root, usage; // 根节点和使用的结点个数
    // int fa[N]; // 记录父亲结点,如果需要的话
public:
    // ...
}

旋转

这里我们记住一张图即可:

从左到右是右旋,从右到左是左旋。

可以发现,这种旋转并不会改变中序遍历的结果(不会影响二叉搜索树的性质)。但是可以影响二叉堆的性质。所以我们可以以此维护二叉堆的性质。

由于我们需要改变
q
或者
p
父节点对其的指向,我们采用引用的方式修改父节点。

后面的Splay也会有旋转的操作,但是两者需要的旋转方式不一样。

这里是将子节点旋转到当前结点
p
上,而splay中的旋转在实现的时候是把当前节点
p
转到父结点上,别混淆了!

void leftRotate(int &p) { // 定义左旋操作
    int q = rc[p];
    rc[p] = lc[q], lc[q] = p;
    p = q; // 更新父节点对此结点的信息
    update(lc[p]), update(p); // 更新结点信息。p已经改变过了!
}

void rightRotate(int &p) { // 定义右旋操作,与上面类似,只是变化了一下lc和rc!
    int q = lc[p];
    lc[p] = rc[q], rc[q] = p, p = q;
    update(rc[p]), update(p);
}

是不是该说一下
update
是个啥?

直接看代码吧:

void update(p) {
    siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p];
}

插入

与二叉搜索树的插入类似。如果遇到已经插入过的结点可以选择新建结点,或者增加标记(
++cnt[p]
),这里选择后者。

我们先来看新建结点的过程:

int newNode(int x, uint prio = 0) {
    ++usage;
    lc[usage] = rc[usage] = 0;
    pri[usage] = prio ? prio : rand();
    val[usage] = x;
    cnt[usage] = siz[usage] = 1;
    return usage;
}

这只是新建一个空结点的操作而已……接下来我们才涉及到插入部分。

新建结点的操作每一种树都很类似,注意灵活修改!

首先我们还是正常的插入,例如我们在刚开始的例子的基础上插入了
(6, 8)

那么根据二叉搜索树的插入方式,插入后应该如下:

很明显,此时不满足二叉堆的性质,我们需要通过旋转的方法来维护。

不难得知,我们需要对
(7, 7)
做一次右旋操作,以使
(6, 8)
成为
(7, 7)
的父节点,从而满足二叉堆的性质。

结果如下:

接着,由于我们一定是在最底部插入的结点,所以我们只需要在回溯的时候一路向上维护二叉堆的性质即可。

代码如下:

void insert(int &p, int x) { // 由于旋转操作需要来自父节点的引用,新建节点也是!
    if (!p) {
        p = newNode(x); // 新建结点
        return;
    }

    if (val[p] == x) { // 有相同结点,增加引用即可
        ++cnt[p], ++siz[p];
        return;
    } else if (val[p] > x) { // 进入左树
        insert(lc[p], x);
        if (pri[p] < pri[lc[p]]) rightRotate(p); // 维护二叉堆性质
    } else { // 进入右树
        insert(rc[p], x);
        if (pri[p] < pri[rp[p]]) leftRotate(p);
    }
    update(p); // 更新信息
}

删除

首先我们先找到需要修改的结点:

void remove(int &p, int x) {
    if (!p) return; // 没有找到要删除的结点
    if (x != val[p]) {
        remove(x < val[p] ? lc[p] : rc[p], x), update(p);
        return;
    }

    // TODO
}

然后我们考虑两种情况:

  • 如果计数大于1,那么我们减少计数,结束即可:

    if (cnt[p] > 1) {
        --cnt[p], --siz[p];
        return;
    }
    
  • 如果计数等于1,那么我们不断再保证二叉堆的性质的情况下不断向下旋转。直到没有子节点,那么我们可以直接
    p = 0
    ,删除即可。

    if (lc[p] || rc[p]) {
        if (rc[p] == 0 || pri[lc[p]] > pri[rc[p]]) {
            rightRotate(p), remove(rp[p], val);
        } else {
            leftRotate(p), remove(lc[p], val);
        }
    } else {
        p = 0;
    }
    

依据逻辑把三个部分合起来即可。

其他操作

例如查找第k大,获取某个数的排名,获取前驱或者后驱。

和二叉搜索树的方法一致,这里就不过多讲述了。

代码链接 此处采用的是另一种写法!注意甄别! Link

FHQ-Treap

首先我们了解一下这个东西和普通的Treap有啥不同:

  • FHQ-Treap基于分裂和合并的操作,代替了旋转,使得可持久化更为容易

  • 操作相对简单,时间复杂度的阶没有变化,还是
    \(O(\log n)\)
    ,但是常数要大一点

我们先来看最重要的分裂部分

分裂

分裂有两种形式

  • 按权值
    v
    分裂:将小于等于
    v
    的所有节点分裂为一棵树,大于
    v
    的放在一棵树

  • 按排名
    k
    分裂:将前
    k
    个数放在一棵树,其他的放在另一颗树。

两者十分类似,代码几乎一模一样,所以这里只细述按权值分裂。

我们还是拿最初的那张图为例子来讲:

假如我们要按权值
4
分裂,也就相当于分成如下两棵树:

按权值
3
分裂,也就相当于分成如下两棵树:

蓝色的表示新建的边,红色的表示断开的边

似乎有点感觉了?我们来细谈分裂的全过程

约定此处红色为左树(权值小于等于
v
),蓝色为右树(权值大于
v
),绿色为下一步进入的结点

x
结点指新入的结点需要拼接到的位置,
y
同样

这里以按权值
3
分裂为例子:

肯定是从根节点开始,明显,根节点的权值
\(\gt 3\)
,所以根节点及其右子树的所有结点都应该放到蓝色树上:

接下来我们判断结点
(3, 8)
,明显,节点的权值
\(\le 3\)
,所以此节点及其左子树都应该放在红色树上,下一步进入结点
(4, 6)

同样的判断,将
(4, 6)
放置在蓝树

下一步的结点为空,结束分裂。

通过观察,我们可以发现分裂后树的相对形态没有改变,所以我们可以尝试着直接在原树上直接分裂,避免复制结点的操作。

在我的代码中,
sync
和其他人写的
pushdown
是一样的,只是我不习惯如此写……所以使用
sync
代替
pushdown
,使用
update
代替
pushup
……

代码如下:

void splitByVal(int p, int v, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要,下传标记!!
    if (val[p] <= x)
        x = p, splitByVal(rc[p], v, rc[p], y);
    else
        y = p, splitByVal(lc[p], v, x, lc[p]);
    update(p);
}

而按照排名分裂十分类似,这里直接给出代码:

void splitByRand(int p, int k, int &x, int &y) {
    if (!p) return (void)(x = y = 0);
    // sync(p); // 如果需要,下传标记!!
    if (siz[lc[p]] < k)
        x = p, splitByRank(rc[p], k - siz[lc[p]] - cnt[p], rc[p], y);
    else
        y = p, splitByRand(lc[p], k, x, lc[p]);
    update(p);
}

合并

由于我们保证了左树的最大值一定不大于右树的最大值,所以我们只需要考虑优先度即可。

那么我们来演示上面分裂后的两棵树合并的过程。

此时
x
,
y
为左树和右树的当前结点。返回的是合并后的结点编号。

首先,
y
的优先度较大,那么此时
y
作为父节点,转而合并
x

y
的左子树,作为
y
的左子树:

此时
x
的优先度较大,所以此时
x
作为父节点,合并
x
的右子树和
y
,作为
x
的右子树。

此时
x
为空,直接接上即可。

至此,合并完成。

合并会遇到的两种情况这里都涉及到了,那么我们来看代码:

int merge(int x, int y) {
    if (!x | !y) return x | y;
    // sync(x), sync(y); // if need
    if (pri[x] > pri[y]) {
        rc[x] = merge(rc[x], y);
        return update(x), x;
    } else {
        lc[y] = merge(x, lc[y]);
        return update(y), y;
    }
    return -1; // NEVER REACH!
}

其他操作

其他操作很容易通过分裂和合并的操作完成,这里讲述思路即可。

  • 插入:新建一个结点作为单独的一棵树,将原树按权值分裂,三者合并即可。

    void insert(int &root, int v) {
        int p = newNode(v);
        int x(0), y(0);
        splitByVal(root, v, x, y);
        root = merge(merge(x, p), y);
    }
    
  • 删除:分裂成三棵树,中间的树结点的权值全部为
    v
    ,分别合并即可。

    void remove(int &root, int v) {
        int x(0), y(0), z(0), tmp(0);
        splitByVal(root, v - 1, x, tmp); // 分裂为 < v 和 >= v 的两棵树
        splitByVal(tmp, v, y, z); // 再分裂为 = v 和 > v 的两棵树
        // 以此避免判断没有v的情况
        root = merge(merge(x, lc[y]), merge(rc[y], z));
    }
    

  • k
    大:按排名分裂即可。

  • 查询排名:按权值分裂(为
    \(\lt x\)

    \(\ge x\)
    的两棵树),使用左树的大小即可。

  • 前驱或者后驱:分裂即可……

整体代码我就不给了,核心就这些了。

Splay

伸展树,由Tarjan(对,就是他)在1985年发明。它与正常的平衡树不同,不能保证每一次的操作在
\(O(\log n)\)
的复杂度内,只能均摊下来
\(O(\log n)\)
。所以说,尽量少用。

Splay最大的特点是每次对一个结点进行操作(读取,或者修改)之后,都会把他转到根节点上。

旋转

我们先来看旋转操作。

还是要记住上面给出的旋转的图,这样方便于理解。这里就不细讲了。

注意和Treap的旋转操作区分开来,这里的旋转是将
当前结点旋转到其父节点的位置

// 0 表示是父节点的左子节点,1表示为右子节点
#define side(x) ((x) == rc[fa[(x)]])
// 利用 side 获取对应的子节点
#define ch(x, k) ((k) ? rc[x] : lc[x])
// rotate x to it's fathers position!
void rotate(int x) {
    int y = fa[x], z = fa[y], k = side(x);
    ch(y, k) = ch(x, k ^ 1);
    if (ch(x, k ^ 1)) fa[ch(x, k ^ 1)] = y;
    ch(x, k ^ 1) = y, fa[y] = x, fa[x] = z;
    if (z) ch(z, y == rc[z]) = x;
    update(y), update(x);
}

在Splay的实现中,
update
操作
没有变化
,还是
siz[p] = siz[lc[p]] + siz[rc[p]] + cnt[p]

伸展

伸展是Splay最最核心的操作,也就是把一个结点旋转到根节点(或者其他地方)。

但是仅仅是一路把当前结点向上旋转就可以了吗?并不是的。

如果仅仅是一路向上,那么会有上图的结果,此时我们只需要来回不断地操作,就可以卡成单次
\(O(n)\)
的复杂度,因此我们不能这么做,所以天才的Tarjan想到了另一种旋转的方法,用以保证其复杂度均摊在
\(O(\log n)\)

对于每一次旋转我们分类讨论:

  • 旋转一次可以到达目的地:直接旋转即可。

  • 至少需要两次旋转:


    • 当前结点与其父节点为同侧:先转父节点,再转子节点。

    • 不同侧,直接两次向上转即可。

那么通过这个规则,我们就可以得到这样一张图:

是不是矮了一点
_

我们可以理解为通过这种规则旋转,每次至多可以减少二分之一的高度,最终下来,高度可以保证在
\(O(\log n)\)
的样子。

所以,伸展的核心代码就可以写出来了:

target指的是向上不停转之后的最终父节点是什么,注意!

void splay(int x, int target) {
    // sync if need!
    // for (int i = x; i; i = fa[i]) stack[++top] = i;
    // while (top) sync(stack[top--]);

    while (fa[x] != target) {
        int y = fa[x], z = fa[y];
        if (z != target) rotate(side(x) == side(y) ? y : x);
        rotate(x);
    }
    if (!target) root = x;
}

其他操作

删除操作非常特殊,后文里会讲,还有,记得每一次无论是查找还是修改什么的,记得把目标节点Splay到根!!!

大部分和二叉搜索树一样。这里不细讲了。

不过这里建议一下Splay的写法细节:

  • 写两个辅助函数,一个用于寻找对于排名的结点,一个用于寻找对于值的结点,都是返回的结点编号。

    int _findVal(int v) {
        int cur = root;
        while (cur) {
            // sync(cur); // if need
            if (val[cur] == v) return cur;
            else if (v < val[cur]) cur = lc[cur];
            else cur = rc[cur];
        }
        return cur; // 0 for not found!
    }
    // return the node index of the kth element
    int _findKth(int k) {
        int cur = root;
        while (cur) {
            // sync(cur); // if need
            if (siz[lc[cur]] >= k) cur = lc[cur];
            else if (siz[lc[cur]] + 1 == k) return cur;
            else k -= siz[lc[cur]] + 1, cur = rc[cur];
        }
        return cur;
    }
    
  • 其他的操作都一定程度上可以基于这两个操作(或者这两个操作的变换)。例如
    remove
    。具体操作看注释

    void remove(int v) {
        int p = _findVal(v);
        if (!p) return;
        splay(p, 0); // 转到根节点
        if (--cnt[p]) return update(p), (void)0; // 减少计数即可
    
        // 如果只有一个子节点,直接作为根节点即可。
        if (!(lc[p] && rc[p])) {
            root = lc[p] | rc[p];
            fa[root] = 0; // 不需要更新!
            return;
        }
    
        // 否则寻找后驱
        int nxt = rc[p]; // sync(nxt); // if need
        while (lc[nxt]) nxt = lc[nxt]/*, sync(nxt) */;
        // 将后驱转到p的右节点的位置
        splay(nxt, p);
        // 此时 lc[nxt] 一定为空,考虑二叉搜索树的性质
        // 所以我们直接把nxt作为根节点,连接原本p的左子树即可。
        lc[nxt] = lc[p];
        update(root = fa[lc[p]] = nxt); // 更新信息
    }
    

其实主要是一些奇怪的操作需要……可恶。

WBLT

这是我最喜欢用的一种平衡树,而且借鉴FHQ-Treap的思路,可以实现类似的操作,这类似的操作这里不细讲。本文只讲述基本。

定义:

  • 叶节点:没有子节点的节点。

  • 内节点:有子节点的节点。

WBLT全称是
Weight Balanced Tree
,有一点类似于
Size Balanced Tree
,只是WBLT是一种
Leafy Tree
,只有叶节点(没有子节点的结点)保存有信息。而其他的内节点都是用于辅助搜索的。

而且WBLT的每一个节点要么是满的,要么是空的。或者说要么左右儿子都有,要么都没有。再或者说内节点既有左节点也有右节点。这使得操作非常方便……

那么内节点如何辅助搜索?在WBLT中,内节点存储的是右节点的值。

语言描述太罗嗦,我们还是直接上图:

结构还是挺一目了然的。

真正保存着信息的其实只有红色圈起来的节点。

不难看出,总共有9个节点,总而言之,如果有
\(n\)
个数据,那么将会有
\(2n - 1\)
个节点。那么我们认为其空间复杂度为
\(O(n)\)
,只是常数为普通平衡树的两倍而已。

搜索

这或许是唯一一个需要从搜索开始讲述的平衡树了

例如我们需要搜索值
3
,那么搜索路径应该是这样的。

由于WBLT内节点保存信息的特性,我们进入下一个节点可以分如下情况讨论:

  • 到达叶子节点:如果当前节点的值等于所需节点的值,那么搜索成功,否则,没有搜到。

  • 在内节点上:如果左子节点的值大于等于目标值,则进入左子树,否则进入右子树。


    其实看图不难发现,当前节点的值就是当前子树中的最大值,所以可以进行上述操作。

这个规则同样适用于其他的操作!请务必画下来试一下!

维护平衡

当然还是需要用到旋转的操作。

别忘了那张图!!!

但是在WBLT中旋转的实现又不一样了。

因为内节点并没有保存实际的信息,所以我们只需要
swap
三次,
update
两次即可。

对了,我好像还没有讲过
update

在WBLT中,有所变化:

void update(int p) {
    if (lc[p]) { // 防止更新叶节点
        // sync(p) // if need
        siz[p] = siz[lc[p]] + siz[rc[p]];
        val[p] = val[rc[p]];
    }
}

为了减少代码,采用了一点奇技淫巧:

#define ch(p, k) (k ? rc[p] : lc[p])
// k 0 left to here, k 1 right to her
// k是0则将左子节点旋转到此处,否则右节点旋转到此处。
// 但是这里没有旋转,只是交换节点而已,简化操作。
void rotate(int p, int k) {
    int q = ch(p, k); // sync(q); // sync if need
    if (!p || !q) return;
    swap(lc[q], rc[q]), swap(lc[p], rc[p]);
    swap(ch(q, k ^ 1), ch(p, k));
    fa[ch(p, k)] = p, fa[ch(q, k ^ 1)] = q;
    update(q), update(p);
}

那么我们考虑如何维护平衡:

其实一般来说,
WBLT
常数本来就小,所以不需要那么严谨的旋转也可以很好的通过很多题。

// 非严谨写法!!!
void fix(int p) {
    const int ratio = 2;
    if (siz[lc[p]] * ratio < siz[rc[p]]) rotate(p, 1); // 左子树太大
    if (siz[rc[p]] * ratio < siz[lc[p]]) rotate(p, 0); // 右子树太大
}

但是为了严谨,肯定不能就这么水过去,
万一有人卡WBLT的常呢??

所以我们还是要稍微严谨一点。

这一部分感谢大佬的文章:
抛弃随机,保持理性——Leafy Tree 到 WBLT - 听风响,闻虫鸣。 - 洛谷博客

在WBLT中,
平衡是加权的
(并不是严格平衡的),一般来说,我们令平衡因子为
\(\alpha\)

那么节点
x
平衡意味着
\(\alpha \cdot siz[x] \lt \min\{siz[lc_x], siz[rc_x]\}\)

不难发现,
\(\alpha\)
应该
\(\le 0.5\)

如果所有节点都满足加权平衡,则这棵树是加权平衡的,并且其高度满足
\(h \le \log_{\frac 1{1-\alpha}}n = O(\log n)\)
。而树高正保证了复杂度。

那么应该如何旋转?很明显,在非严谨写法中已经体现出了雏形了:
哪一棵子树大就把那一棵子树转上来

但是观察上图可以知道
b
所在的子树
相对位置是不会变的
,也就是说如果
\(siz_a \lt \alpha \cdot (siz_a + siz_b + siz_c)\)
,并且
\(siz_c < \alpha \cdot (siz_a + siz_b + siz_c)\)
,旋转之后任然不满足加权平衡。

所以此时我们应该把
b
向上转一下,然后再进行类似的维护。

这里讲的相对感性,更严谨的证明请参考上面给出的文章

操作类似于:

相当于把
b
阉割成俩,然后分别和
a, c
在一起……

所以我们可以得出如下代码:

#define ch(p, k) (k ? rc[p] : lc[p])
void fix(int p, double ratio = 0.29) {
    int d;
    if (siz[lc[p]] < siz[p] * ratio) d = 1;
    else if (siz[rc[p]] < siz[p] * ratio) d = 0;
    else return;
    int q = ch(p, d);
    if (siz[ch(q, d)] < siz[p] * ratio) rotate(q, d ^ 1);
    rotate(p, d);
}

插入

还是以上图为例。不妨假设我们需要插入
3
,那么自然我们到了原来
3
所在的节点。那么我们如何变成两个呢?

很明显,将当前节点作为父节点,左右节点分别为当前节点的值和新增的值。

记得保证左节点不大于右节点的值

然后回溯更新即可。

void insert(int x) {
    if (!root) {
        root = newNode(x, 0);
        return;
    }

    int cur = root;
    while (true) {
        // sync(cur); // if needed
        if (!lc[cur]) { // new node down here!
            int y = val[cur];
            if (x > y) swap(x, y); // make sure x < y
            // 第二个参数是将其父节点设为cur!和Treap的newNode声明不一样了
            lc[cur] = newNode(x, cur), rc[cur] = newNode(y, cur);
            break;
        }
        cur = (x > val[lc[cur]]) ? rc[cur] : lc[cur];
    }

    while (cur) {
        update(cur), fix(cur);
        cur = fa[cur];
    }
}

删除

我们还是先找到要删除的值所对应的节点吧(任意一个)。

那么我们用其兄弟节点直接替代其父节点即可。

兄弟节点指的是其父节点的另一个子节点

听着很简答吧。在纸上画一下先!!

参考代码:

// 这一块的代码未经编译验证!!可能会有问题
void copyFrom(int p, int q) {
    lc[p] = lc[q], rc[p] = rc[q];
    fa[lc[p]] = fa[rc[p]] = p;
    val[p] = val[q], siz[p] = siz[q];
}

void remove(int p, int x) {
    if (!p) return;
    if (val[lc[p]] >= x) {
        if (siz(lc[p]) == 1 && val[lc[p]] == val) {
            // _del(rc[p]), _del(lc[p]); 标记回收节点,如果需要的话(记得别清空,copyFrom需要用!)
            copyFrom(p, lc[p]);
        } else {
            remove(lc[p], val), update(p), fix(p);
        } 
    } else {
        if (siz(rp) == 1 && val(rp) == val) {
            // _del(lp), _del(rp);
            copyFrom(p, rc[p]);
        } else {
            remove(rc[p], val), update(p), fix(p);
        }
    }
}

当然,你也可以写成非递归的形式,这里就不展示了。

其他操作

其实我觉得其他操作都很简单,不想多说,掌握了二叉搜索树的算法,应该自然就会了。

这里就直接展示部分基础操作的代码吧。

// 统计所有 < x 的值的个数,也可以用于获取排名
int count(int x) {
    int cur(root), cnt(0);
    while (cur) {
        if (siz[cur] == 1) return cnt;
        else if (val[lc[cur]] >= val) cur = lc[cur];
        else cnt += siz[lc[cur]], cur = rc[cur];
    }
}

int kth(int k) {
    int cur(root);
    while (cur) {
        if (siz[cur] == 1) return k == 1 ? val[cur] : -1; // -1: not found!
        else if (siz[lc[cur]] >= k) cur = lc[cur];
        else k -= siz[lc[cur]], cur = lc[cur];
    }
}

int getpre(int val) {
    return kth(count(val));
}

int getpost(int val) {
    return kth(count(val + 1) + 1);
}


到这里,你应该学会了四种在OI中较为常用的平衡树了吧。

那么模板题肯定可以用四种方法过了吧:

哦,文艺平衡树啊,并不是一种平衡树,它可以通过FHQ-Treap或者Splay实现,拓展的WBLT也可以实现
(只是这里没有讲)


附赠各种树速度比较(基于正常平衡树随机数据的操作):

Splay < FHQ-Treap < Treap < WBLT < Better-Optimized FHQ-Treap

+ ?? 阳寿随机种子Treap

更加优化的Treap参考:
treap怎样跑得更快 - zx2003 的博客 - 洛谷博客