蓝桥杯线段树模板题——区间修改、区间查询

🚀 每日一题，冲刺国赛 🚀

---

题目导航：

区间修改、区间查询

🎇思路：线段树

🔱思路分析：

本题涉及到了对区间操作的问题，因此，我们可以用线段树解决

step:

首先定义线段树 : tree=[0]*(n<<2)

1. 建树

def build(p,pl,pr):
    if pl==pr:
        tree[p]=a[pl] # 更新叶子结点
        return
    mid=(pl+pr)>>1
    build(p<<1,pl,mid)
    build(p<<1|1,mid+1,pr)
    tree[p]=tree[p<<1]+tree[p<<1|1] # 更新父结点

2. 更新
   $update$用于更新区间的值，把区间内所有元素的值加上 $d$，如果 $tree[p]$这棵子树完全被包含在所要修改的区间 $[L,R]$内，只需要对根结点 $tree[p]$打上懒标记 $tag$即可，不需要继续往下修改$p$的子结点

   
   

   ①打标记addtag

   给结点打上懒标记+更新结点的值

   代码实现：

   def addtag(p,pl,pr,d):
       tag[p]+=d # 给p结点打上懒标记
       tree[p]+=d*(pr-pl+1) # 更新p结点（p结点为子树的根节点）
   

   
   

   ②push_down

   如果 $tree[p]$这棵子树不能完全包含在 $[L,R]$中，但是在之前的修改中又已经给 $tree[p]$打上了懒标记，那么为了解决冲突，需要用 $pus{h}_{d}own$进行解决:

   
   

   key：将根节点的tag向下传递给左右子树

   代码实现：

   def push_down(p,pl,pr):
       if tag[p]!=0: # 之前对p进行过修改，有懒标记
           mid=(pl+pr)>>1
           addtag(p<<1,pl,mid,tag[p]) # 将懒标记传递给左结点
           addtag(p<<1|1,mid+1,pr,tag[p]) # 将懒标记传递给右结点
           tag[p]=0 # 清空p结点的懒标记
   

   
   

   ③更新：

   def update(p,L,R,pl,pr,d): # 将区间[L,R]加上d
       if L<=pl and R>=pr:
           addtag(p,pl,pr,d) # 更新所包含子树的根节点
           return
       mid=(pl+pr)>>1
       if L<=mid:
           update(p<<1,L,R,pl,mid,d)
       if R>mid:
           update(p<<1|1,L,R,mid+1,pr,d)
       tree[p]=tree[p<<1]+tree[p<<1|1]
   

3. 查询

区间查询时，要对查询的区间结点消除 $tag$标记，这样才是当前该区间的真实值

代码实现：

def query(p,L,R,pl,pr):
    if L<=pl and R>=pr: # 要查询的区间[L,R]包含了当前的[pl,pr]
        return tree[p] # 返回这个结点的值

    push_down(p,pl,pr) # 向下传递懒标记（一路向下更新结点值）

    mid=(pl+pr)>>1
    ans=0
    if L<=mid:
        ans+=query(p<<1,L,R,pl,mid) # 得到满足条件的左子树的和
    if R>mid:
        ans+=query(p<<1|1,L,R,mid+1,pr) # 得到满足条件的右子树的和
    return ans

完整代码实现：

# 1.建树
def build(p,pl,pr):
    if pl==pr:
        tree[p]=a[pl] # 更新叶子结点
        return
    mid=(pl+pr)>>1
    build(p<<1,pl,mid)
    build(p<<1|1,mid+1,pr)
    tree[p]=tree[p<<1]+tree[p<<1|1] # 更新父结点


# addtag
def addtag(p,pl,pr,d):
    tag[p]+=d # 给p结点打上懒标记
    tree[p]+=d*(pr-pl+1) # 更新p结点（p结点为子树的根节点）

# push_down
def push_down(p,pl,pr):
    if tag[p]!=0: # 之前对p进行过修改，有懒标记
        mid=(pl+pr)>>1
        addtag(p<<1,pl,mid,tag[p]) # 将懒标记传递给左结点
        addtag(p<<1|1,mid+1,pr,tag[p]) # 将懒标记传递给右结点
        tag[p]=0 # 清空p结点的懒标记

# 2.查询query
def query(p,L,R,pl,pr):
    if L<=pl and R>=pr: # 要查询的区间[L,R]包含了当前的[pl,pr]
        return tree[p] # 返回这个结点的值

    push_down(p,pl,pr) # 向下传递懒标记（一路向下更新结点值）

    mid=(pl+pr)>>1
    ans=0
    if L<=mid:
        ans+=query(p<<1,L,R,pl,mid) # 得到满足条件的左子树的和
    if R>mid:
        ans+=query(p<<1|1,L,R,mid+1,pr) # 得到满足条件的右子树的和
    return ans

# 3.更新update
def update(p,L,R,pl,pr,d): # 将区间[L,R]加上d
    if L<=pl and R>=pr:
        addtag(p,pl,pr,d) # 更新所包含子树的根节点
        return
    mid=(pl+pr)>>1
    if L<=mid:
        update(p<<1,L,R,pl,mid,d)
    if R>mid:
        update(p<<1|1,L,R,mid+1,pr,d)
    tree[p]=tree[p<<1]+tree[p<<1|1]

N,Q=map(int,input().split())
a=[0]+list(map(int,input().split())) # 叶子结点数组(0不存)
tree=[0]*(len(a)<<2) # 线段树
tag=[0]*(len(a)<<2) # 懒标记


build(1,1,N)

res=[]
for _ in range(Q):
    li=list(map(int,input().split()))
    if len(li)==3:
        res.append(query(1,li[1],li[2],1,N))
    elif len(li)==4:
        update(1,li[1],li[2],1,N,li[3])

for i in res:
    print(i)
t(map(int,input().split()))
    if len(li)==3:
        res.append(query(1,li[1],li[2],1,N))
    elif len(li)==4:
        update(1,li[1],li[2],1,N,li[3])

for i in res:
    print(i)

---

 

🎇此题为线段树模板题，今天的考点是~🎇

线段树！