news 2026/9/1 22:11:18

基于卡尔曼滤波的视频目标跟踪实战:运动小球轨迹平滑

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
基于卡尔曼滤波的视频目标跟踪实战:运动小球轨迹平滑

简介:本资源是一套面向计算机视觉初学者与图像处理实践者的卡尔曼滤波视频跟踪教学实践包,聚焦运动小球这一典型目标,解决噪声干扰下目标位置估计不稳、轨迹跳变等实际跟踪难题,适用于课程设计、毕业设计及算法入门项目。压缩包共4个文件(24.15MB),含一段实拍小球运动视频(MP4)、一段带标注的测试序列(AVI)、核心MATLAB实现代码(.m)及图文并茂的程序说明文档(DOCX),分别支撑效果演示、算法验证、代码复现与原理理解全流程。已有562人学习下载,资源提供从图像预处理(背景抑制与颜色特征提取)、状态向量定义(位置+速度)、系统/观测矩阵构建,到Q/R参数调优与轨迹可视化对比的完整闭环,代码可直接运行,文档详述各模块作用与关键参数物理意义,便于读者掌握卡尔曼滤波在动态目标跟踪中的建模逻辑与工程落地要点。 先说实话,做视频目标跟踪的人,十有八九都绕不开卡尔曼滤波。你拿到的这个“基于卡尔曼滤波的视频跟踪,基于卡尔曼滤波的运动小球跟踪(代码完整,数据齐全)”项目,我第一眼看到标题就知道它解决了什么痛点:单帧检测结果噪声大、目标偶尔丢帧、轨迹跳来跳去,而卡尔曼滤波恰好能在这些情况下把轨迹“圆”回来。这篇文章我尽量不写成教科书,而是按实际动手做的顺序,把原理、代码、参数调优和踩坑记录全部摊开讲,适合刚接触卡尔曼滤波的学生,也适合做机器人视觉、工业检测想快速用上跟踪方案的工程师。

我会以Python实现为线索(MATLAB版本思路完全一致,只是矩阵接口不同),带你从一段绿色小球视频开始,逐步搭出一个能实时输出平滑轨迹的跟踪器。代码块我会拆开解释,参数怎么拍、为什么这么拍,都给你交代清楚。

1. 项目概述与整体设计思路

1.1 标题背后的真实需求拆解

“视频跟踪”这四个字听起来简单,实际上拆开看,有三个独立的问题:第一,每一帧图像里怎么找到目标,这叫目标检测;第二,目标在帧与帧之间怎么移动,这叫运动建模;第三,多个候选目标怎么和已有的轨迹对上号,这叫数据关联。很多人一上来就啃卡尔曼滤波,其实卡尔曼滤波只负责第二件事——运动建模和状态估计。

运动小球跟踪是这个领域最经典的入门场景,因为它把检测问题简化到了极致:一个颜色鲜明的球,用HSV阈值就能抠出来,背景不用考虑。这样整个项目的注意力就能全放在卡尔曼滤波本身。我拿到代码后先做的事就是区分“哪里是检测模块,哪里是滤波模块”,如果你也想复现,建议你也先做这件事。

这个项目最完整的地方是数据齐全:既有合成视频,也有从实际摄像头采集的序列。为什么强调数据?因为没有统一的数据,你很难判断算法改对了没有。我在调参时经常用同一段小球视频来回跑,这样对比效果才公平。

1.2 方案选型:为什么是卡尔曼滤波

做跟踪,可选方案不少,但各有各的脾气。我把常见的几个方案放一起对比,这样选型逻辑就清晰了。

方案计算量对遮挡鲁棒性模型假设适用场景
均值滤波/滑动平均极低信号平滑,不解决预测
卡尔曼滤波线性高斯运动匀速/匀加速目标,实时系统
粒子滤波任意非线性非高斯复杂多峰场景,精度要求高
光流法中高图像亮度恒定稠密运动估计,不适合单目标逻辑
深度学习跟踪(SiamRPN类)高(需GPU)数据驱动通用目标,但要有训练算力和数据

小球运动在帧间时间极短,用匀速模型(CV,Constant Velocity)近似完全够用。卡尔曼滤波在这里的最大优势是:它不只是对当前帧结果做平滑,还能根据上一帧的运动趋势预测下一帧目标大概在哪里,就算检测器偶尔漏检,滤波器也能给出一个不太离谱的位置当“兜底”。这一点是均值滤波做不到的。

另外要注意,卡尔曼滤波假设噪声是高斯分布、运动模型是线性的。如果小球轨迹是正弦摆动或圆周运动,匀速模型就会出现系统性偏差,这时要么加大过程噪声Q去“容忍”模型误差,要么换EKF/UKF。但入门先跑通线性版本,再谈扩展。

1.3 系统流水线:一个跟踪器是怎么工作的

整个系统可以抽象成一条流水线,我习惯按以下顺序组织代码:

  1. 读入一帧图像,做预处理(去噪、颜色空间转换)。
  2. 用HSV阈值提取疑似小球区域,计算轮廓中心作为“观测值”。
  3. 如果这是第一帧,用观测值初始化卡尔曼滤波器的状态向量。
  4. 如果已有滤波器,执行“预测”步骤,得到目标位置的先验估计。
  5. 将检测到的观测值和预测位置做最近邻匹配(单目标场景通常只有一个观测)。
  6. 执行“更新”步骤,融合预测和观测,得到当前帧最优估计。
  7. 把滤波后的坐标画在图像上,同时记录轨迹点,输出可视化结果。

这个流程初看简单,但真正的坑都在第3、5、6步。比如第一帧要不要初始化?观测丢失时是继续更新还是只预测?匹配距离超过多少算“新目标”?后面我会逐一说明。

2. 卡尔曼滤波原理精讲:5个公式吃透预测-校正闭环

2.1 先用一个生活例子建立直觉

卡尔曼滤波干的事,可以类比成你在开车时的定位判断。车速表告诉你按当前速度,车子应该到了哪个位置,但车速表有累计误差;GPS告诉你当前位置,但GPS有随机噪声。真正靠谱的位置,不是单信任何一个,而是把两个来源做个加权融合。车速表越可信,就越信预测;GPS越准,就越信观测。

这个“加权融合”的权重就是卡尔曼增益K。它不是定死的,而是每一帧都根据两个不确定度重新算:过程噪声Q(模型有多不可信)和测量噪声R(传感器有多不可信)。理解了这句话,后面的公式就都有了解释。

2.2 状态向量与运动模型定义

运动小球的经典做法,是把状态向量定义成4维:

x = [px, py, vx, vy]^T

也就是水平位置、垂直位置、水平速度、垂直速度。相邻两帧间隔时间为dt(比如30fps视频就是1/30秒),在匀速模型下,状态转移矩阵F写成:

F = [[1, 0, dt, 0], [0, 1, 0, dt], [0, 0, 1, 0], [0, 0, 0, 1]]

观测矩阵H把4维状态映射到2维观测,因为我们能检测到的是位置,测不到速度:

H = [[1, 0, 0, 0], [0, 1, 0, 0]]

有人会问,为什么不能只把位置放进状态里?能,但如果只有位置,就没有速度信息去预测下一帧,滤波效果和滑动平均差不多,遇到丢帧就没辙。带上速度后,即使检测丢失两三帧,也能按最后速度继续外推。

2.3 五个核心公式与实际含义

卡尔曼滤波每一帧就做两件事:预测和更新。预测对应前两个公式,更新对应后三个公式。

预测步骤:

  1. 状态预测:x_pred = F @ x_last。这是让状态按运动模型走一步。

  2. 协方差预测:P_pred = F @ P_last @ F.T + Q。P矩阵表示当前状态的可信度,对角线越大越不确定。加上Q表示:即便模型完全正确,也存在外界随机扰动,不确定度在预测后会增加。

更新步骤:

  1. 计算卡尔曼增益:K = P_pred @ H.T @ inv(H @ P_pred @ H.T + R)。K是核心,它告诉系统“预测和观测各信几分”。R越大,K越小,越倾向信预测;Q越大,P_pred越大,K越大,越倾向信观测。

  2. 状态更新:x_new = x_pred + K @ (z - H @ x_pred)。括号里是“观测值和预测值的差异”,叫残差或新息。K乘以残差,就是修正量。

  3. 协方差更新:P_new = (I - K @ H) @ P_pred。融合观测后,不确定度下降,这个公式就是把这个变化记录下来。

代码里我用numpy实现这五步,每行对应一个公式,调试起来非常直接。

import numpy as np dt = 1.0 / 30.0 F = np.array([[1, 0, dt, 0], [0, 1, 0, dt], [0, 0, 1, 0], [0, 0, 0, 1]], dtype=np.float32) H = np.array([[1, 0, 0, 0], [0, 1, 0, 0]], dtype=np.float32) class KalmanFilter2D: def __init__(self, init_pos, init_vel=(0, 0), q=0.01, r=1.0): self.x = np.array([init_pos[0], init_pos[1], init_vel[0], init_vel[1]], dtype=np.float32).reshape(-1, 1) self.P = np.eye(4, dtype=np.float32) * 10.0 self.Q = np.eye(4, dtype=np.float32) * q self.Q[0, 0] = q * dt**3 / 3.0 self.Q[1, 1] = q * dt**3 / 3.0 self.Q[0, 2] = q * dt**2 / 2.0 self.Q[2, 0] = q * dt**2 / 2.0 self.Q[1, 3] = q * dt**2 / 2.0 self.Q[3, 1] = q * dt**2 / 2.0 self.Q[2, 2] = q * dt self.Q[3, 3] = q * dt self.R = np.eye(2, dtype=np.float32) * r def predict(self): self.x = F @ self.x self.P = F @ self.P @ F.T + self.Q return self.x[0, 0], self.x[1, 0] def update(self, zx, zy): z = np.array([zx, zy], dtype=np.float32).reshape(-1, 1) y = z - H @ self.x S = H @ self.P @ H.T + self.R K = self.P @ H.T @ np.linalg.inv(S) self.x = self.x + K @ y self.P = (np.eye(4, dtype=np.float32) - K @ H) @ self.P return self.x[0, 0], self.x[1, 0]

这段代码里的Q矩阵不是简单赋值,而是按连续白噪声模型离散化得到的。很多人图省事直接用q*np.eye(4),那样会把速度噪声和位置噪声同等对待,效果差不少。第一次跑通后,建议试试把Q的公式改成笨办法,对比一下轨迹平滑度,你会明显看到差别。

2.4 初始化参数:P0、Q、R的量纲直觉

参数初始化是新手最容易翻车的地方。我的经验是:

  • P0:初始不确定度。设太大会让前几帧修正过猛,轨迹跳一下;设太小会让滤波器“自以为是”,观测新息半天融不进去。10到100的量级作为起点都没问题。
  • Q:过程噪声方差。它描述“匀速模型到底有多不可信”。小球被外力碰了一下、转了个弯,这些都属于Q要吸收的误差。Q越小,轨迹越平滑,但也越迟钝。
  • R:测量噪声方差。它描述“检测位置有多不准”。如果小球轮廓提取稳定,R可以设小一点,比如1;如果图像噪声大、轮廓抖动明显,R要调到10以上。

图像坐标是像素单位,所以Q和R也要配合像素尺度。如果图像是640x480,位置测量噪声一般不到1个像素,R=1合理;如果图像缩小到320x240,位置噪声也会降,R可以相应调小。

3. 运动小球跟踪完整实现:从视频帧到平滑轨迹

3.1 数据准备与小球检测

项目里“数据齐全”是什么意思?我理解是包含两类视频:一类是程序合成的小球动画,这类视频的好处是能提供真值坐标,用于定量评估滤波误差;另一类是真实摄像头拍摄的实景视频,背景有光照变化和噪声干扰,用来测试算法鲁棒性。

检测部分,我用OpenCV的HSV颜色空间提取绿色小球,核心思路是:转换颜色空间 -> 设置阈值生成掩膜 -> 形态学去噪 -> 找轮廓 -> 算质心。

import cv2 import numpy as np def detect_ball(frame): hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV) lower_green = np.array([35, 80, 60]) upper_green = np.array([85, 255, 255]) mask = cv2.inRange(hsv, lower_green, upper_green) mask = cv2.erode(mask, None, iterations=2) mask = cv2.dilate(mask, None, iterations=2) contours, _ = cv2.findContours(mask, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE) if not contours: return None largest = max(contours, key=cv2.contourArea) if cv2.contourArea(largest) < 20: return None M = cv2.moments(largest) if M["m00"] == 0: return None cx = int(M["m10"] / M["m00"]) cy = int(M["m01"] / M["m00"]) return (cx, cy)

HSV阈值有个大坑:H分量在OpenCV里范围是0到179,不是0到360。我第一次做的时候把绿色H范围设成90到150,结果什么都检测不到,因为OpenCV里纯绿的H在60附近。后来我都是用取色器直接点一下目标区域,再上下浮动20个H值,这样最稳。

3.2 主循环:检测、预测、更新三步走

主循环是跟踪器的骨架。每一帧里,我先用detect_ball拿到观测坐标(可能为None),然后分三种情况处理:

  1. 滤波器还没初始化:如果是第一帧,就用观测位置初始化状态向量,速度和P都用默认值。这一步只能做一次,千万别在循环里反复初始化。
  2. 观测存在:先执行predict(),再用观测值执行update()。
  3. 观测丢失:只执行predict(),用预测结果继续输出。同时统计连续丢失帧数,超过阈值就认为目标彻底丢失,重置滤波器。
tracker = None lost_frames = 0 max_lost_frames = 20 cap = cv2.VideoCapture("ball_sequence.mp4") while True: ret, frame = cap.read() if not ret: break obs = detect_ball(frame) if tracker is None and obs is not None: tracker = KalmanFilter2D(init_pos=obs) if tracker is not None: pred_pos = tracker.predict() if obs is not None: filt_pos = tracker.update(obs[0], obs[1]) lost_frames = 0 else: filt_pos = pred_pos lost_frames += 1 if lost_frames > max_lost_frames: tracker = None cv2.circle(frame, (int(pred_pos[0]), int(pred_pos[1])), 8, (255, 0, 0), 2) cv2.circle(frame, (int(filt_pos[0]), int(filt_pos[1])), 4, (0, 0, 255), -1) if obs is not None: cv2.circle(frame, obs, 3, (0, 255, 255), -1) cv2.imshow("Kalman Track", frame) if cv2.waitKey(30) & 0xFF == 27: break

这段代码里我用了三种颜色的圆:红色是滤波结果,蓝色是预测点,黄色是观测点。调试的时候把这三个点同时画出来非常有用——一眼就能看出系统是“信预测多”还是“信观测多”。

3.3 数据评估:用RMSE指标验证滤波效果

只有视频没有真值,很难说滤波到底改进了什么。项目里的合成视频自带真值坐标,我参照它写了个RMSE评估脚本。RMSE是均方根误差,公式很简单:

RMSE = sqrt(mean((x_filter - x_truth)^2 + (y_filter - y_truth)^2))

实际跑下来,观测轨迹的RMSE和滤波轨迹的RMSE对比一般会这样:在目标匀速运动时,RMSE下降20%到40%左右;在目标突然转向时,滤波轨迹短暂滞后,RMSE反而可能变大。这不代表滤波不行,而是匀速模型在转向瞬间本来就会有偏差,加大Q之后适应速度会快一点,代价是平滑度下降。

如果你拿到的数据没有真值,也有一个土办法验证:把视频暂停在某帧,对比预测位置和检测位置是否合理。如果预测点基本都在观测点附近,说明Q和R配得还行。

3.4 MATLAB版本实现要注意什么

如果你是MATLAB用户,整个逻辑完全一样,但要留意两个差异。第一,MATLAB矩阵下标从1开始,而Python从0开始,画图时坐标别搞混。第二,MATLAB里卡尔曼滤波可以用control系统工具箱的kalman函数封装好,但建议先自己写5个公式,至少一遍,这样才能理解每一步在干什么。

MATLAB里np.linalg.inv对应inv(),F @ P @ F.T对应FPF',reshape(-1,1)对应(:)。我见过有人直接用高斯过程的matlab包,结果参数调不明白,因为没理解底层实现。

4. 参数调优与实战效果分析

4.1 Q和R:一个控制平滑,一个控制响应

参数调优是整个项目里最需要“手感”的部分。我把Q和R的调参经验整理成一个表格,方便你根据现象反推该调哪个参数。

现象可能原因调整方案
轨迹太抖,跟随噪声跳R设置偏小,太信观测增大R,比如从1调到5
轨迹太平滑,转弯跟不上Q设置偏小,模型太自信增大Q,比如从0.01调到0.1
观测丢失后外推太快Q偏大或速度估计偏大减小Q,或者降低速度初值
启动前几帧轨迹跳变严重P0偏大或观测噪声大减小P0,或先跳过前3帧再初始化
跟踪点落后真实位置R偏大,滤波响应慢减小R,让观测权重加大

调参时我习惯一次只调一个参数。如果你同时动Q和R,出问题都不知道怪谁。我做了一个自动化对比脚本:固定一段视频,循环遍历q在0.001到1之间的对数刻度,每跑一次记录RMSE,然后画曲线看最低点。这比肉眼调快得多。

4.2 遮挡与目标丢失:经典场景怎么处理

小球被手挡住是最常见的干扰场景。因为在遮挡期间没有观测,系统只能靠predict()外推。外推位置会逐渐偏离真实位置,尤其当球从匀速变成急停或者转向时。

我的做法是加一个“置信度”机制:连续丢帧超过3帧后,不再把预测结果当成最终输出画实线,而是画虚线,提醒用户这可能是估计位置。重新检测到目标后,不要直接使用update(),因为此时预测位置可能已经漂远,新观测距离预测位置很远,直接融合会导致轨迹突变。

解决办法是设定一个关联门限,比如上一帧预测位置和当前观测点距离超过50像素时,认为丢失太久,重新初始化滤波器,而不是继续沿用旧状态。

def gating_distance(pred, obs, threshold=50.0): return np.hypot(pred[0] - obs[0], pred[1] - obs[1]) < threshold

这个阈值不是拍脑袋定死的,它和视频分辨率、小球运动速度都有关。如果小球速度很快,一帧能跑30像素,阈值至少要按两到三帧的运动幅度来设,否则会误判为“丢失太久”。

4.3 多目标扩展:从单滤波器到多滤波器

单目标跟踪跑通后,很多项目自然要扩展成多目标。多目标的核心问题是“数据关联”:检测到了好几个球,哪个球匹配哪个滤波器?

最简单的策略是最近邻匹配:对每个滤波器预测位置,计算它和所有检测框的距离,取最近的观测进行更新。但当目标靠近、交叉时,最近邻容易跟错。更高阶的做法是用匈牙利算法做全局最优匹配,把代价矩阵建好,用scipy.optimize.linear_sum_assignment一行求解。

多个滤波器就是维护一个列表,每个滤波器有独立的状态、独立的丢帧计数。每帧都做预测,再做匹配,最后按匹配结果更新。这部分代码量不大,但调试起来很费神,建议先用两个小球不交叉的视频测,再逐步加大难度。

4.4 实时性能优化

卡尔曼滤波本身计算量极低,5个公式都是小矩阵运算,跑不到1毫秒。实时性能瓶颈反而在检测部分:HSV阈值全图扫描和轮廓提取是最耗时的。

如果帧率不够,我有几个常用的优化手段:

  • 把图像缩到一半分辨率再检测,比如640x480缩到320x240,检测速度快好几倍。
  • 用感兴趣区域(ROI)限制检测范围。如果小球只在画面中央运动,就只在中央区域找,能省大量计算。
  • 用上一帧滤波位置作为中心,只在该点周围一定半径内做检测。这叫“跟踪引导检测”,对速度不太快的目标非常有效。

5. 常见问题与排查技巧实录

5.1 新手最容易踩的6个坑

这个项目我已经带过几拨人复现,问题集中在几个固定位置,我整理出来供你对照排查。

问题概率原因与解决
检测不到小球HSV阈值不对,或没做形态学处理;建议先用取色器取色
跟踪框抖动严重滤波参数R过小,或者初始化时速度给得不合理
目标跟丢后找不到丢帧期间只预测不校正,位置漂移超出关联门限;调大Q或调大门限
轨迹画到画面外面丢帧太久导致外推位置出界;应设置最大丢帧数并重置
程序报矩阵维度错误检查x是不是4x1、P是不是4x4、Q和R维数是否对齐
实时性太卡检测部分耗时长,先缩小图像再做处理

5.2 调试工具:把中间状态“可视化”

我最常用的调试方法是“三圆同显”:在每一帧同时画观测点(黄)、预测点(蓝)、滤波后位置(红)。三条线放在一起,滤波器到底信谁、延迟多少、目标丢失时外推方向对不对,全都一目了然。

另外,把P矩阵对角线值实时打印出来,能帮你理解状态不确定度的变化。正常情况是:predict()之后不确定度增大,update()之后不确定度下降。如果你看到P一直增大不下降,说明系统长期没有有效观测,滤波器已经“飘了”。

5.3 从线性到非线性:下一步进阶方向

如果你做完这个小球跟踪想继续往深走,我建议按这个顺序进阶:

  • 扩展卡尔曼滤波(EKF):把匀速模型换成圆周运动或摆锤运动模型,在非线性运动场景更准。
  • 无损卡尔曼滤波(UKF):处理强非线性模型,比如四元数表示姿态时,EKF线性化误差太大,UKF更稳定。
  • 联邦卡尔曼滤波:多个传感器独立滤波后做信息融合,适合多摄像头接力跟踪同一个目标。
  • 误差状态卡尔曼滤波(ESKF):IMU和视觉融合定位的常用方案,机器人SLAM方向会大量用到。

这些方向每一个都可以单独写一篇长文,但共同的基础就是你现在跑通的这套预测-更新闭环。

我个人在实际操作中的体会是:卡尔曼滤波这套东西,光看公式永远学不会,必须亲手把代码跑起来,再故意调坏几个参数看效果,才能形成直觉。你现在手里既然有完整代码和齐全数据,最值得做的事就是反复折腾Q和R,把“平滑”和“响应”这对矛盾体会透彻。把这一步做扎实了,后面学EKF、UKF都会快很多。最后再分享一个小技巧:调试时一定把预测点、观测点、滤波点同时画出来,这三个点的相对位置几乎能告诉你所有答案。

本文还有配套的精品资源,点击获取

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/9/1 22:10:57

【OFDM通信】高速铁路场景下的OTFS与 OFDM性能对比Matlab仿真

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f447; 关注我领取海量matlab电子书和…

作者头像 李华
网站建设 2026/9/1 22:09:59

【单片机毕设案例分享】基于单片机的环境参数采集与智能加湿报警系统设计 基于 STM32 或 51 单片机的语音声光双重提示加湿控制系统开发(024905)

博主介绍&#xff1a;✌️码农一枚 &#xff0c;专注于大学生项目实战开发、讲解和毕业&#x1f6a2;文撰写修改等。全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于单片机&#xff0c;STM32单片机&#xff0c;51单片机&#xff0c;J…

作者头像 李华
网站建设 2026/9/1 22:09:58

open62541 V1.1编译与Server/Client联调实战笔记

简介&#xff1a;本资源是面向工业自动化与物联网领域C/C开发者的OPC UA开源实现open62541-V1.1完整分发包&#xff0c;专为构建跨平台、安全可靠的OPC UA服务器与客户端提供开箱即用支持。压缩包共11个文件&#xff0c;涵盖源码&#xff08;.c/.h&#xff09;、多平台二进制发…

作者头像 李华
网站建设 2026/9/1 22:09:04

乐信2020数据笔试题拆解:数据岗四维能力模型与解题攻略

“乐信2020校园招聘数据笔试题”这个标题&#xff0c;乍一看只是一场校招的技术考核&#xff0c;但把它拆开看&#xff0c;其实能琢磨出不少东西。金融科技公司招数据分析师&#xff0c;笔试题目往往不是单纯考“会不会写代码”&#xff0c;而是考“能不能用数据解决业务问题”…

作者头像 李华
网站建设 2026/9/1 22:03:51

树状数组精讲:从二进制索引到逆序对与第K小问题

树状数组&#xff08;Binary Indexed Tree&#xff0c;又称 Fenwick Tree&#xff09;是一种轻量级的区间数据结构&#xff0c;常用于单点更新和前缀和查询。它能把一次更新或一次查询从 O(n) 降到 O(log n)&#xff0c;而且代码量只有十来行&#xff0c;非常适合在算法题、实时…

作者头像 李华
网站建设 2026/9/1 22:02:54

腾讯音乐暑期实习笔试复盘:后端开发算法题与备考策略

收到腾讯音乐娱乐&#xff08;TME&#xff09;2023暑期实习生招聘技术类笔试&#xff08;I&#xff09;的邀请邮件&#xff0c;是在一个工作日的下午。我当时正在图书馆里刷LeetCode&#xff0c;看到邮箱提醒弹出来&#xff0c;第一反应是确认考试时间&#xff0c;第二反应是有…

作者头像 李华