[백준 10999번] 구간 합 구하기 2 (Python3)

import sys
input = sys.stdin.readline

def make(i,v,s,e,x):
  seg[x] += v
  if s==e:
    return
  mid = (s+e)//2
  if i<=mid:
    make(i,v,s,mid,x*2)
  else:
    make(i,v,mid+1,e,x*2+1)

def update(i,j,v,s,e,x):
  seg[x] += lazy[x]*(e-s+1)+v*(j-i+1)
  if s!=e:
    lazy[x*2] += lazy[x]; lazy[x*2+1] += lazy[x]
  lazy[x] = 0
  if s==i and j==e:
    if s!=e:
      lazy[x*2] += v; lazy[x*2+1] += v
    return seg[x]
  mid = (s+e)//2
  if j<=mid:
    return update(i,j,v,s,mid,x*2)
  if i>mid:
    return update(i,j,v,mid+1,e,x*2+1)
  return update(i,mid,v,s,mid,x*2)+update(mid+1,j,v,mid+1,e,x*2+1)

N,M,K = map(int,input().split())
seg = [0]*4*N; lazy = [0]*4*N
for i in range(N):
  make(i,int(input()),0,N-1,1)
for _ in range(M+K):
  q,*a = map(lambda x:int(x)-1,input().split())
  if q:
    print(update(*a,0,0,N-1,1))
  else:
    update(*a[:-1],a[-1]+1,0,N-1,1)

느리게 갱신되는 세그먼트트리 기본문제

Lazy propagation이라는 알고리즘https://baeharam.github.io/posts/algorithm/lazy-propagation/을 이용한다.