def pushUp(rt):
summ[rt] = summ[rt*2]+summ[rt*2+1]
return
def pushDown(l,r,rt):
#print(rt)
if update[rt]:
update[rt*2]=1
update[rt*2+1]=1
change[rt*2]=change[rt]
change[rt*2+1]=change[rt]
lazy[rt*2]=0
lazy[rt*2+1]=0
summ[rt*2]=change[rt]*l
summ[rt*2+1]=change[rt]*r
update[rt]=0
if lazy[rt]!=0:
lazy[rt*2]+=lazy[rt]
summ[rt*2]+=l*lazy[rt]
lazy[rt*2+1]+=lazy[rt]
summ[rt*2+1]+=lazy[rt]*r
lazy[rt]=0
def build(l,r,rt):
#print(l,r,rt)
if l==r:
summ[rt]=arr[r]
return
mid=(l+r)//2
build(l,mid,rt*2)
build(mid+1,r,rt*2+1)
pushUp(rt)
def add(l,r,c,L,R,rt):
if l<=L and r>=R:
summ[rt]+=c*(R-L+1)
lazy[rt]+=c
return
mid=(R+L)//2
pushDown(mid-l+1,r-mid,rt)
if l<=mid:
add(l,r,c,L,mid,rt*2)
if r>mid:
add(l,r,c,mid+1,R,rt*2+1)
pushUp(rt)
def upDate(l,r,c,L,R,rt):
if l<=L and r>=R:
update[rt]=1
change[rt]=c
summ[rt]=(R-L+1)*c
lazy[rt]=0
return
mid=(R+L)//2
pushDown(mid-l+1,r-mid,rt)
if l<=mid:
upDate(l,r,c,L,mid,rt*2)
if r>mid:
upDate(l,r,c,mid+1,R,rt*2+1)
pushUp(rt)
def query(l,r,L,R,rt):
if l<=L and r>=R:
return summ[rt]
mid=(R+L)//2
pushDown(mid-l+1,r-mid,rt)
ans=0
if l<=mid:
ans+=query(l,r,L,mid,rt*2)
if r>mid:
ans+=query(l,r,mid+1,R,rt*2+1)
return ans
s=[1,2,3,4,5,6,7,8,9,10]
n=len(s)
arr=[0 for i in range(n+1)]
for i in range(1,n+1):
arr[i]=s[i-1]
lazy=[0 for i in range(4*n)]
summ=[0 for i in range(4*n)]
update=[0 for i in range(4*n)]
change=[0 for i in range(4*n)]
build(1,n,1)#将s构造成一棵线段树
#add(4,7,10,1,n,1)#将4到7的数加10
#upDate(4,7,20,1,n,1)#将4到7的数更新为20
print(query(4,7,1,n,1)) #输出4到7范围数的和
