type
status
date
slug
summary
tags
category
icon
password
comment

一维数组定义

二维数组定义

树状数组

  • 普通树状数组维护的信息及运算要满足结合律可差分,如加法(和)、乘法(积)、异或等。
  • 树状数组能解决的问题是线段树能解决的问题的子集:树状数组能做的,线段树一定能做;线段树能做的,树状数组不一定可以。然而,树状数组的代码要远比线段树短,时间效率常数也更小,因此仍有学习价值。
  • 区间长度:从 a[1] 开始构造数组,其中 c[x] 的数组代表 a[x-k+1]a[x] 的信息,区间长度 klowbit(x)
  • 区间查询:利用 前缀和 & 差分 的方式,以和为例贴出对应代码
  • 三条性质:
      1. 对于,要么有c[x]c[y]不交,要么有c[x]包含于c[y]
      1. c[x]真包含于c[x+lowbit(x)]
      1. 对于任意,有c[x]c[y]不交
    • 总结: 事实上,树状数组的树形态是 xx+lowbit(x) 连边得到的图,其中 x+lowbit(x) 是的 x 父亲。
      • notion image
  • 单点修改:修改c[x]和他的所有祖先
  • 建树:转化为n次单点修改
    • Tricks: 方法一:每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献,即每次确定完儿子的值后,用自己的值更新自己的直接父亲。
      方法二:预处理前缀和,直接计算c数组
  • 区间修改:建立了两个差分树状数组,所用函数不变,计算方式发生改变,详情见此博客 贴出我的python代码:
Enabling Conversational Interaction with Mobile UI using Large Language ModelsLlamaTouch: A Faithful and Scalable Testbed for Mobile UI Task Automation
Loading...
E1ainay
E1ainay
淡泊明志,宁静致远🍃
公告
🎉Welcome to My Blog🎉
📖I’m currently a junior in the University of Electronic Science and Technology of China(UESTC),majoring in Software Engineering.
💡This blog is used to record my learning experiences.
🥳If you have any suggestions,I’d be very glad to communicate with you!