当前位置：首页 > news >正文

25.5.22学习总结

news 来源：原创 2025/6/29 12:14:22

ST表（Sparse Table，稀疏表）是一种用于高效解决静态区间最值查询（RMQ）问题的数据结构。其核心思想是通过预处理每个长度为2^j的区间的最值，使得查询时只需合并两个子区间的最值即可得到结果，从而实现O(1)的查询复杂度。

一、核心特性

预处理时间复杂度：O(nlog⁡n)
查询时间复杂度：O(1)
适用场景：静态数据（无修改操作）的区间最值查询。
支持操作：可重复贡献且可结合的运算（如最大值、最小值、最大公约数等）。

二、构建过程

初始化：
- 定义二维数组st，其中st[i][j]表示从位置i开始、长度为2j的区间的最值。
- 初始时，st[i][0] = arr[i]（即长度为1的区间的最值为元素本身）。
动态规划填充：
- 对于每个j（1≤j≤⌊log⁡2n⌋），遍历所有可能的起点i，满足i+2j−1<n。
- 状态转移方程：
  
  st[i][j]=op(st[i][j−1],st[i+2j−1][j−1])其中op为合并操作（如取最大值或最小值）。

三、查询过程

对于区间[L,R]的最值查询：

计算区间长度：len=R−L+1。
确定最大幂次：k=⌊log⁡2len⌋。
合并子区间结果：

result=op(st[L][k],st[R−2k+1][k])这两个子区间分别覆盖[L,L+2k−1]和[R−2k+1,R]，确保完全覆盖原区间。

四、优缺点分析

优点：
- 查询速度快（O(1)）。
- 适用于多次查询静态数据的场景。
缺点：
- 不支持动态修改。
- 仅适用于可重复贡献的操作。

五、ST表与线段树的比较

1. 时间复杂度对比

操作	ST表	线段树
预处理	O(nlog⁡n)	O(n)
查询	O(1)	O(log⁡n)
更新	不支持	O(log⁡n)

ST表：查询极快（常数时间），但预处理稍慢，且不支持动态修改。
线段树：查询和更新均为对数时间，支持动态数据。

2. 空间复杂度对比

数据结构	空间复杂度
ST表	O(nlog⁡n)
线段树	O(n)

ST表：需要二维数组存储预处理结果，空间消耗较大。
线段树：通常用一维数组实现（类似堆），空间更优。

3. 功能对比

功能	ST表	线段树
静态区间最值（RMQ）	✔️	✔️
动态区间最值/和	❌	✔️
区间更新	❌	✔️
可扩展性	❌	✔️

4. 适用场景

选择ST表：
- 数据静态不变，且需要极快查询（如高频RMQ）。
- 无需支持修改操作。
- 例如：离线处理大量查询的RMQ问题。
选择线段树：
- 数据动态变化，需要支持更新。
- 查询类型复杂（如区间和、区间最值混合）。
- 例如：实时更新的数据库区间统计。

六、例题

【模板】ST 表 && RMQ 问题https://www.luogu.com.cn/problem/P3865

25.5.22学习总结

ST表（Sparse Table，稀疏表）是一种用于高效解决静态区间最值查询（RMQ）问题的数据结构。其核心思想是通过预处理每个长度为2^j的区间的最值，使得查询时只需合并两个子区间的最值即可得到结果，从而…...

编程日记 2025/6/29 12:14:22

接口自动化测试框架(pytest+allure+aiohttp+ 用例自动生成)

🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快近期准备优先做接口测试的覆盖，为此需要开发一个测试框架，经过思考，这次依然想做点儿不一样的东西。接口测试是比较讲究效率的…...

编程日记 2025/6/27 22:49:32

FastAPI在 Nginx 和 Docker 环境中的部署

目录实现示例1. 项目结构2. FastAPI 应用 (app/main.py)3. 依赖文件 (app/requirements.txt)4. Dockerfile5. Nginx 配置 (nginx/nginx.conf)6. Docker Compose 配置 (docker-compose.yml) 使用方法修改代码后更新实现示例接下来创建一个简单的示例项目，展示如何…...

编程日记 2025/6/27 16:05:26

08 接口自动化-用例管理框架pytest之fixtrue,conftest.py,allure报告以及logo定制

文章目录一、使用fixture实现部分前后置1.function级别:在每个函数的前后执行2.class级别：在每个类的前后执行一次3.module级别：在每个模块的前后执行一次4.package、session级别，一般是和connftest.py文件一起使用二、当fixture的级别为pa…...

编程日记 2025/6/27 23:24:44

Appium+python自动化（二）- 环境搭建—下

简介我这里已经将android的测试开发环境已经搭建准备完毕。上一篇android测试开发环境已经准备好， 那么接下来就是appium的环境安装和搭建了。搭建环境安装过程中切勿浮躁，静下心来一个一个慢慢地按照步骤一个个来。环境装好后，可以用真机…...

编程日记 2025/6/27 4:20:21

浅谈测试驱动开发TDD

目录 1.什么是TDD 2.TDD步骤 3.TDD 的核心原则 4.TDD 与传统开发的对比 5.TDD中的单元测试和集成测试区别 6.总结 1.什么是TDD 测试驱动开发（Test-Driven Development，简称 TDD） 是一种软件开发方法论，核心思想是 “先写测试…...

编程日记 2025/6/27 23:15:35

MVC和MVVM架构的区别

MVC和MVVM都是前端开发中常用的设计模式，都是为了解决前端开发中的复杂性而设计的，而MVVM模式则是一种基于MVC模式的新模式。 MVC(Model-View-Controller)的三个核心部分：模型、视图、控制器相较于MVVM(Model-View-ViewModel)的三个核心部分…...

编程日记 2025/6/27 4:08:52

网络安全-等级保护(等保) 3-1-1 GB/T 28448-2019 附录A (资料性附录)测评力度附录C(规范性附录)测评单元编号说明

附录A (资料性附录)测评力度 A.1 概述测评力度是在等级测评过程中实施测评工作的力度，体现为测评工作的实际投入程度，具体由测评的广度和深度来反映。测评广度越大，测评实施的范围越大，测评实施包含的测评对象就越多。测评深度…...

编程日记 2025/6/27 23:12:18

MySQL 可观测性最佳实践

MySQL 简介 MySQL 是一个广泛使用的开源关系型数据库管理系统（RDBMS），以其高性能、可靠性和易用性而闻名，适用于各种规模的应用，从小型网站到大型企业级系统。监控 MySQL 指标是维护数据库健康、优化性能和确保数据…...

编程日记 2025/6/29 11:59:51

深入解析Spring Boot与Redis集成：高效缓存与性能优化

深入解析Spring Boot与Redis集成：高效缓存与性能优化引言在现代Web应用中，缓存技术是提升系统性能的重要手段之一。Redis作为一种高性能的内存数据库，广泛应用于缓存、会话管理和消息队列等场景。本文将详细介绍如何在Spring Boot项目中集…...

编程日记 2025/6/27 23:27:29

《C 语言字符串操作从入门到实战（下篇）：strncpy/strncat/strstr 等函数原理与实现》

目录七. strncpy函数的使用与模拟实现 7.1 strncpy函数理解 7.2 strncpy函数使用示例 7.3 strncpy函数模拟实现八. strncat函数的使用与模拟实现 8.1 strncat函数理解 8.2 strncat函数使用示例 8.3 strncat函数模拟实现九. strncmp函数的使用 9.1 strncmp函数理…...

编程日记 2025/6/29 12:09:56

百度智能云千帆AppBuilder RAG流程技术文档

一、概述本文档旨在详细阐述百度智能云千帆AppBuilder的RAG（Retrieval-Augmented Generation，检索增强生成）流程，包括API对接、知识库维护以及文档资料管理等关键环节。通过本流程，开发者可以高效地构建基于大模型的…...

编程日记 2025/6/29 10:07:32

程序编辑器快捷键总结

程序编辑器快捷键总结函数跳转函数跳转 Creator : F2VSCode : F12visual Studio : F12...

编程日记 2025/6/27 23:13:28

MySQL中实现大数据量的快速插入

一、SQL语句优化 1. 批量插入代替单条插入单条插入会频繁触发事务提交和日志写入，效率极低。批量插入通过合并多条数据为一条SQL语句，减少网络传输和SQL解析开销。 -- 低效写法：逐条插入 INSERT INTO table (col1, col2) VALUE…...

编程日记 2025/6/29 11:59:52

从零基础到最佳实践：Vue.js 系列（8/10）：《性能优化与最佳实践》

引言 Vue.js 是一个轻量、灵活且易于上手的现代前端框架，因其响应式数据绑定和组件化开发而广受欢迎。然而，随着项目规模的增长，性能问题逐渐显现，例如首屏加载缓慢、页面渲染卡顿、内存占用过高等。性能优化不仅能提升用户体验&…...

编程日记 2025/6/27 23:37:08

这个题可以使用欧拉降幂，1000000007是质数，所以欧拉函数值为1000000006. import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System…...

编程日记 2025/6/27 22:49:59

Mysql的MVCC机制

MySQL的MVCC机制主要通过以下几个关键要素来工作： 数据版本与隐藏列 - MySQL InnoDB存储引擎会在每行数据中添加几个隐藏列，用于实现MVCC。其中包括 DB_TRX_ID 列，记录最后一次修改该行数据的事务ID； DB_ROLL_PTR 列&#xff…...

编程日记 2025/6/27 23:23:18

spring中的BeanFactoryAware接口详解

一、接口定义与核心作用 BeanFactoryAware 是 Spring 框架提供的一个回调接口，允许 Bean 在初始化阶段获取其所属的 BeanFactory 实例。该接口定义如下： public interface BeanFactoryAware {void setBeanFactory(BeanFactory beanFactory) throws Bea…...

编程日记 2025/6/27 22:48:51

mysql 创建用户，创建数据库，授权

创建一个远程用户 create user test% identified by test1111; 创建一个数据库并指定编码 create database testdb CHARACTER SET utf8mb4 COLLATE utf8mb4_general_ci; 授权 grant all privileges on testdb.* to test%; 应用更改： FLUSH PRIVILEGES; 注意…...

编程日记 2025/6/27 22:48:44

Android 网络全栈攻略（三）—— 从三方库原理来看 HTTP

前面两篇文章我们介绍了 HTTP 协议的请求方法、请求码以及常用的请求头/响应头的知识。本篇会从 OkHttp 配置的角度来看这些框架是如何实现 HTTP 协议的，目的是加深对 HTTP 的理解，并学习协议是如何落地的。我们会选取 OkHttp 中与协议实现相关的源码作为…...

编程日记 2025/6/27 22:48:45

BlazeMeter录制jmeter脚本

文章目录 chrome安装blazeMeter插件开始录制 chrome安装blazeMeter插件开始录制 1、点击重置按钮 2、输入名称 3、点击开始录制 4、打开浏览器操作 5、回到录制页面点击stop(注意，不要在第四步操作的那个窗口点停止) 6、点击save 7、保存jmeter脚本 8、将jmeter脚…...

编程日记 2025/6/27 3:38:39

SQL的RAND用法和指定生成随机数的范围

SQL中的RAND函数能够满足多种随机数生成的需求。通过合理地使用种子、结合一些SQL语句，我们可以实现灵活的随机数生成。在数据填充、数据处理、数据分析中经常需要用RAND生成的随机数。用法1 生成随机浮点数，其返回值在0（包括0）…...

编程日记 2025/6/27 22:59:30

PHP7内核剖析学习笔记第七章面向对象

面向对象编程，简称OOP，是一种程序设计思想。面向对象把对象作为程序的基本单元，一个对象包含了数据和操作数据的函数。面向对象一直是软件开发领域内比较热门的话题，它更符合人类看待事物的一般规律。与Java不同，PHP并…...

编程日记 2025/6/27 19:41:43

地信GIS专业关于学习、考研、就业方面的一些问题答疑

整理了地信GIS专业学生问得最多的几个问题：关于GIS专业学习、考研以及就业方面；大家可以一起来探讨一下。学习方面 1、作为一名GISer需要哪些核心素养或能力？ 答：GIS是个交叉学科，涉及到地理学、地质学、测绘、遥感…...

编程日记 2025/6/27 23:01:57

构建可重复的系统 - SRE 的 IaC 与 CI/CD 基础

构建可重复的系统 - SRE 的 IaC 与 CI/CD 基础还记得我们在第一篇提到的 SRE 核心原则之一——减少琐事 (Toil) 吗？想象一下手动配置服务器、部署应用程序、管理网络规则……这些任务不仅耗时、重复，而且极易出错。当系统规模扩大时，手动操作很快就会变得难以为继。SRE 的核…...

编程日记 2025/6/27 22:49:05

CQF预备知识：一、微积分 —— 1.2.2 函数f(x)的类型详解

文中内容仅限技术学习与代码实践参考，市场存在不确定性，技术分析需谨慎验证，不构成任何投资建议。 📖 数学入门全解本教程为复习课程，旨在帮助读者复习数学知识。教程涵盖以下四个主题： 微积分线性代数微…...

编程日记 2025/6/27 22:50:09

PyQt学习系列03-动画与过渡效果

PyQt学习系列笔记（Python Qt框架） 第三课：PyQt的动画与过渡效果一、动画与过渡效果概述 1.1 动画与过渡的区别动画（Animation）：用于描述对象属性随时间变化的过程（如位置、颜色、大小&…...

编程日记 2025/6/27 22:48:54

偏微分方程数值方法指南及AI推理

偏微分方程（PDE）是我们用来描述科学、工程和金融领域中各种现象的语言——从流体流动和热传递到波的传播和金融衍生品的定价。然而，这些方程的解析解通常难以获得，尤其是在处理复杂几何形状或非线性行为时。这时，数值方…...

编程日记 2025/6/27 23:34:30

flask允许跨域访问如何设置

flask允许跨域访问在Flask中，允许跨域访问通常涉及到CORS（跨源资源共享）策略。Flask本身并不直接提供CORS支持，但你可以通过安装和使用第三方库如Flask-CORS来轻松实现跨域资源共享。安装Flask-CORS 首先，你需要安装Flask-CORS。你可以使用pip来安装它： pip instal…...

编程日记 2025/6/27 23:14:02

深度学习模型部署：使用Flask将图像分类（5类）模型部署在服务器上，然后在本地GUI调用。（全网模型部署项目步骤详解：从模型训练到部署再到调用）

个人github对应项目链接： https://github.com/KLWU07/Image-classification-and-model-deployment 1.流程总览 2.图像分类的模型—Alexnet 3.服务器端部署及运行 4.本地PyCharm调用—GUI界面一、流程总览本项目方法还是使用Flask 库，与之前一篇机器学…...

编程日记 2025/6/27 23:40:28

在Pycharm中如何安装Flask

（推荐）方法一：在Pycharm中创建项目之后，再安装Flask 1：在创建Pycharm时，解释器类型选择第一个：项目venv（自动生成的虚拟环境），在左下角选择终端（…...

编程日记 2025/6/27 23:40:07

基于Scikit-learn与Flask的医疗AI糖尿病预测系统开发实战

引言在精准医疗时代，人工智能技术正在重塑临床决策流程。本文将深入解析如何基于MIMIC-III医疗大数据集，使用Python生态构建符合医疗AI开发规范的糖尿病预测系统。项目涵盖从数据治理到模型部署的全流程，最终交付符合DICOM标准的临床决策支…...

编程日记 2025/6/27 23:25:44

解决前端路由切换导致Keycloak触发页面刷新问题

使用window.location.href进行页面跳转时,浏览器会完全刷新页面,这会导致当前的JavaScript上下文被清空。如果你的登录状态依赖于某些临时存储(如LocalStorage或sessionStorage),而这些存储在页面刷新后未正确初始化或丢失,就会导致用户被认为未登录。触发keycloak再次登录导…...

编程日记 2025/6/27 23:30:01

基于大模型的胫腓骨干骨折全周期预测与治疗方案研究报告

目录一、引言 1.1 研究背景与意义 1.2 研究目的与创新点 1.3 国内外研究现状二、大模型技术原理与应用基础 2.1 大模型的基本架构与算法 2.2 医疗数据的收集与预处理 2.2.1 数据收集 2.2.2 数据预处理 2.3 模型训练与优化 2.3.1 模型训练过程 2.3.2 参数调整与超…...

编程日记 2025/6/27 2:42:23

智慧交通的核心引擎-车牌识别接口-车牌识别技术-新能源车牌识别

在数字化与智能化浪潮席卷交通运输领域的今天，车牌识别接口功能正以其精准、高效的特性，成为构建智慧交通体系的关键技术支撑。通过自动采集、识别车牌信息并实现数据互通，该功能已被深度融入交通管理、物流运输、出行服务等多个场景&#xf…...

编程日记 2025/6/27 23:34:18

小白的进阶之路系列之三----人工智能从初步到精通pytorch计算机视觉详解上

计算机视觉是教计算机看东西的艺术。例如，它可能涉及构建一个模型来分类照片是猫还是狗（二元分类）。或者照片是猫、狗还是鸡（多类分类）。或者识别汽车出现在视频帧中的位置（目标检测）。或者找出图像中不同物体可以被分离的位置（全视分割）。计算机视觉应用在…...

编程日记 2025/6/27 23:24:47

手写简单的tomcat

首先，Tomcat是一个软件，所有的项目都能在Tomcat上加载运行，Tomcat最核心的就是Servlet集合，本身就是HashMap。Tomcat需要支持Servlet，所以有servlet底层的资源：HttpServlet抽象类、HttpRequest和HttpRespon…...

编程日记 2025/6/29 11:55:48

院校机试刷题第九天：P1042乒乓球、回顾代码随想录第二天

定位一下刷题计划：刷题全面——代码随想录过一遍，刷到模拟题——刷洛谷普及组-。所以还是每天刷一个代码随想录，外加两道洛谷，题目先从官方题单【算法1-1】开始。一、P1042乒乓球 1.解题思路关键点1：输入形式输…...

编程日记 2025/6/27 23:26:27

如何在 Mac M4 芯片电脑上卸载高版本的 Node.js

文章目录一、确认 Node.js 的安装方式二、卸载 Node.js 的通用步骤1. 通过官方安装包（.pkg）安装的 Node.js2. 通过 Homebrew 安装的 Node.js3. 通过 nvm 安装的 Node.js 三、验证是否卸载成功四、推荐使用 nvm 管理 Node.js 版本五、常见问题1. 卸载后仍…...

编程日记 2025/6/27 23:37:12

基础IO详解

FILE 1.FILE是文件的用户级数据结构，创建在堆上 2.FILE里有维护一个用户级缓冲区，这个用户级缓冲区是为了减少系统调用的次数 3.进程一般会有三个标准FILE*流，stdin，stdout，stderr，对应文件描述符一般是…...

编程日记 2025/6/27 23:29:05

QT入门基础

QT作为一个C的GUI框架，编程语法和C都差不多，上手还是比较快的。但是学习一个新的技术，总有一些新的概念是不清楚的，所以需要先了解一下这些概念。 1、QT软件系 QT：安装时会指定某个版本的QT，这个QT指QT库…...

编程日记 2025/6/27 23:17:46

【TI MSP430与SD NAND：心电监测的长续航解决方案】

在医疗科技飞速发展的今天，心电监测设备已成为守护人们心脏健康的关键防线。而在这一领域，Nordic、TI、ST、NXP 等行业巨头凭借其深厚的技术积累和创新精神，推出的主芯片与 SD NAND 存储组合方案，正引领着心电监测技术的变革&…...

编程日记 2025/6/27 23:03:40

中医方剂 - 理中汤

理中汤是中医经典方剂，出自《伤寒论》，由人参（或党参）、干姜、白术、炙甘草四味药组成。一、核心功效与作用机理 1. 温中散寒（核心作用） 表现：脘腹冷痛、呕吐清水、腹泻完谷不化现代对应&a…...

编程日记 2025/6/27 23:07:53

遨游三防科普：三防平板是什么？有什么特殊功能？

在极端环境作业与专业领域应用中，传统消费级电子设备往往因环境适应性不足而“折戟沉沙”。三防平板的诞生，正是为破解这一难题而生，它通过军用级防护标准与专业化功能设计，成为工业巡检、地质勘探、应急救援等场景的核心工具。所…...

编程日记 2025/6/28 21:56:59

关于数据仓库、数据湖、数据平台、数据中台和湖仓一体的概念和区别

我们谈论数据中台之前， 我们也听到过数据平台、数据仓库、数据湖、湖仓一体的相关概念，它们都与数据有关系，但他们和数据中台有什么样的区别， 下面我们将围绕数据平台、数据仓库、数据湖和数据中台的区别进行介绍。一、相关概念…...

编程日记 2025/6/27 23:28:39

FPGA：CLB资源以及Verilog编码面积优化技巧

本文将先介绍Kintex-7系列器件的CLB（可配置逻辑块）资源，然后分享在Verilog编码时节省CLB资源的技巧。以下内容基于Kintex-7系列的架构特点，并结合实际设计经验进行阐述。一、Kintex-7系列器件的CLB资源介绍 Kintex-7系列是Xilin…...

编程日记 2025/6/27 23:02:42

AUTOSAR AP 入门0：AUTOSAR_EXP_PlatformDesign.pdf

AUTOSAR AP官网：AUTOSAR Adaptive Platform设计AUTOSAR AP的目的，翻译版官方文档 AUTOSAR_EXP_PlatformDesign.pdf ： https://mp.weixin.qq.com/s?__bizMzg2MzAyMDIzMQ&mid2247553050&idx2&sn786c3a1f153acf99b723bf4c9832acaf …...

编程日记 2025/6/27 23:01:35

WPF 常见坑：ContentControl 不绑定 Content 时，命令为何失效？

WPF 中的 Content“{Binding}” 到底有多重要？一次被忽视的绑定导致命令无法触发的案例分析在使用 WPF 构建 UI 时，我们经常会使用 ContentControl、ItemsControl、DataTemplate 等机制进行灵活的界面布局。但很多开发者可能会在某些场景中遇到这样的问…...

编程日记 2025/6/29 5:16:52