手机版网站开发价格,wordpress数据库缓存,园林景观设计公司,论我国门户网站建设不足树状数组 拜读了大佬的讲解博文#xff08;树状数组(详细分析应用)#xff0c;看不懂打死我!#xff09;#xff0c;写一篇Python版的笔记巩固消化#xff0c;附带蓝桥杯历年真题作为例题演示 一、作用
用于快速读取列表中 某个区间内所有元素的和 实现单点修改#xff…树状数组 拜读了大佬的讲解博文树状数组(详细分析应用)看不懂打死我!写一篇Python版的笔记巩固消化附带蓝桥杯历年真题作为例题演示 一、作用
用于快速读取列表中 某个区间内所有元素的和 实现单点修改区间查询 若以差分数组作为a[]则可实现 区间修改单点查询 操作是一个常用技巧
二、时间复杂度
传统方式
访问某个元素 O ( 1 ) O(1) O(1)获得某区间元素和 O ( n ) O(n) O(n)
树状数组
访问某个元素 O ( l o g n ) O(logn) O(logn)获得某区间元素和 O ( l o g n ) O(logn) O(logn)
三、规则
通过创建一个列表t记录以二进制划分的区间内元素的和其中lowbit(x)的位数决定本节点所处的层数t[x]保存了以x为根的子树中叶节点的值即区间的元素和 通过观察 a数组具有以下性质
下标索引从1开始切记长度为n t数组具有以下性质 t [ x ] t[x] t[x] 节点覆盖的长度是 l o w b i t ( x ) lowbit(x) lowbit(x) t [ x ] t[x] t[x] 的父节点是 t [ x l o w b i t ( x ) ] t[x lowbit(x)] t[xlowbit(x)]树的深度为 l o g 2 n 1 log_2n 1 log2n1 t [ x ] t[x] t[x] 节点覆盖的区间为 [ x − l o w b i t ( x ) 1 , x ] [x-lowbit(x)1, x] [x−lowbit(x)1,x] t [ x ] t[x] t[x] 也即等于 t [ x ] t[x] t[x] 的子节点区间以后到$ a[x]$ 的所有元素之和! t [ x ] ≡ ∑ i x − l o w b i t ( x ) 1 x a [ i ] t[x] \equiv \sum_{i x-lowbit(x)1}^x a[i] t[x]≡∑ix−lowbit(x)1xa[i]
四、创建和维护树状数组的三个基本函数
树状数组不是标准库中的数据结构而是一个通过特殊函数维护和操作的一维数组。要想在题目中使用树状数组首先需要创建三个操作函数。以下是这三个函数的详解。
1取最低二进制位函数 lowbit()
lowbit()函数用于获取一个正整数在二进制表示下最低位的1与其右侧所有的0所构成的二进制数的数值。 例如 12 2 ′ b 1100 , l o w b i t ( 12 ) 2 ′ b 100 4 12 2b1100, lowbit(12) 2b100 4 122′b1100,lowbit(12)2′b1004
# 正负x按位与
def lowbit(x):return (-x)x2单点修改函数 add()
为了实现树状数组的单点修改操作需要创建一个函数add()。 由于每一个树上节点的祖先节点的值都包含了该节点的值所以在修改某一个点的时候需要从叶子节点开始逐级向上递归修改它所有祖先节点的值。 这里就需要根据当前节点的序号 i i i 找出其双亲节点的序号由树状数组的性质可知其双亲结点的序号为 i l o w b i t ( i ) ilowbit(i) ilowbit(i)见规则2
def add(x,v):global n # n len(t)while x n:t[x] vx lowbit(x)3区间查询函数 ckeck()
建立树状数组后就可以利用其性质进行快速的区间查询了由 规则4 可推知区间[1,x]的元素和等于 t [ 1 ] ⋅ ⋅ ⋅ t [ x − l o w b i t ( x ) ] t [ x ] t[1] ··· t[x-lowbit(x)] t[x] t[1]⋅⋅⋅t[x−lowbit(x)]t[x]由此可以使用递推求出区间和
# 求出区间[1:x1]内所有元素的和
def check(x):ans 0while x 0:ans t[x]x - lowbit(x)return ans以上函数无法指定区间的左端点为了求出指定端点的区间和可以使用类似于前缀和的方法求出指定区间的和值
# 求出区间[x:y]内所有元素的和
def check(left,right):ans 0x right - 1# 先使用原方法求出区间[1:right]的区间和while x 0:ans t[x]x - lowbit(x)# 然后减去区间[1:left]的元素和即可获得答案x left-1while x 0:ans - t[x]x - lowbit(x)return ans五、树状数组整体模板
1单点修改、区间查询模板
def lowbit(x):return x(-x)def add(x,v):global n,twhile x n:t[x] vx lowbit(x)def check(left, right):global tx right - 1ans 0while x 0:ans t[x]x - lowbit(x)x left - 1while x 0:ans - t[x]x - lowbit(x)return ans # 创建原数组和树状数组
# 注意树状数组的序号从1开始
a [0] [int(i) for i in input().split()]
n len(a)
t [0]*n
# 初始化树状数组
# 方法和初始化前缀和数组类似将每一位的元素加到t[]中
for i in range(1,n):add(i,a[i])
# 查询修改前的区间和
print(check(2,6))
# 修改原数组中某一元素的值单点修改
index,value map(int,input().split())
add(index, value)
# 查询修改后的区间和区间查询
print(check(2,6))
# 具体功能略按照题目要求编写2区间修改、单点查询模板
def lowbit(x):return x(-x)
def add(x,v):global x,twhile x n:t[x] v
def check(left,right):global n,tx right - 1while x 0:ans t[x]x - lowbit(x)x left - 1while x 0:ans - t[x]x - lowbit(x)return
# 初始化原数组和树状数组
a [0] [int(i) for i in input().split()]
n len(a)
t [0]*(n1)
d [0]*(n1)
# 用树状数组维护差分数组
for i in range(1,n):d[i] a[i] - a[i-1]add(i,d[i])
# 区间修改
l,r,v map(int,input().split())
# 结合差分数组修改的原理在树状数组上进行单点修改
# 修改d[l],d[r1]
add(l,v)
add(r1,-v)
# 单点查询
# 查询原数组第三个元素的值
print(check(3))六、例题
例题一异或和蓝桥杯第14届省赛
问题描述 给一棵含有 n n n 个结点的有根树根结点为 1 1 1 编号为 i i i 的点有点权 a i a_i ai i ∈ [ 1 , n ] i \in [1,n] i∈[1,n]。现在有两种操作格式如下 1 x y 1 x y 1xy 该操作表示将点 x x x 的点权改为 y y y。 2 x 2 x 2x 该操作表示查询以结点 x x x 为根的子树内的所有点的点权的异或和。 现有长度为 m m m 的操作序列请对于每个第二类操作给出正确的结果。 输入格式: 输入的第一行包含两个正整数 n , m n,m n,m 用一个空格分隔。第二行包含 n n n 个整数 $a_1, a_2, … ,a_n 相邻整数之间使用一个空格分隔。接下来 n − 1 n−1 n−1 行每行包含两个正整数 u i , v i u_i, v_i ui,vi表示结点 u i u_i ui 和 v i v_i vi之间有一条边。接下来 m m m 行每行包含一个操作。 输出格式: 输出若干行每行对应一个查询操作的答案。 # 求 DFS 序以便建立树状数组
cnt 0
def dfs(cur,pre):# cur 是当前节点的序号pre是上一个节点的序号global cntcnt 1# 记录将当前节点压入栈中的时间戳seq[cur][0] cnt for i in tree[cur]:if pre ! i:dfs(i,cur)# 记录将当前元素出栈的时间戳自此以后的时间戳均与以cur为根节点的树无关seq[cur][1] cnt # 树状数组函数三件套
def lowbit(x):return x(-x)def modify(x,v):global nwhile x n:t[x] ^ v # 计算异或和x lowbit(x)def query(x):global nans 0while x 0:ans ^ t[x]x - lowbit(x)return ans# 接收输入创建数据结构
n,m map(int,input().split())
# a[]存储每一个点的权值
a [0] [int(i) for i in input().split()]# 用邻接表存储树结构
tree [[] for i in range(n1)]
for _ in range(n-1):u,v map(int,input().split())# 注意没说方向是一个无向边tree[u].append(v)tree[v].append(u)# 创建一个二维数组seq[][]记录DFS序
# 其中seq[i]是有2个元素的列表两个元素分别是第i个节点入栈和出栈的时间戳
seq [[0,0] for i in range(n1)]
dfs(1,0)# 为DFS序数组创建树状数组并用a[]的值初始化
t [0]*(n1)
for i in range(1,n1):modify(seq[i][0], a[i])
for _ in range(m):instr [int(i) for i in input().split()]if instr[0] 1:# 修改元素注意到需要在赋值的同时清除原有元素所以将原值与新值异或相当于清除原值modify(seq[instr[1]][0], a[instr[1]]^instr[2])# 维护a[]确保其始终保存着每一个节点的当前值a[instr[1]] instr[2]else:# 输出单点查询结果 print(query(seq[instr[1]][1]) ^ query(seq[instr[1]][0] - 1))
