[백준 1321번] 군인 (Python3)

import sys
input = sys.stdin.readline

def updatefen(i,v):
  while i<=M:
    fen[i] += v
    i += i&-i

def find(x,i,c):
  if x<=fen[i] and i<=N and x>fen[i]-data[i]:
    return i
  if x>fen[i]:
    return find(x-fen[i],i+(1<<c),c-1)
  return find(x,i-(1<<c),c-1)

N = int(input()); M = 1<<19
data = [0]+[*map(int,input().split())]

fen = [0]*(M+1)
for i in range(1,N+1):
  updatefen(i,data[i])

for _ in range(int(input())):
  q,*a = map(int,input().split())
  if q==1:
    updatefen(a[0],a[1]); data[a[0]] += a[1]
  else:
    print(find(*a,M,18))

= 사탕상자 [백준 2243번] 사탕상자 (Python3) (tistory.com) = 데이터 구조 [백준 12899번] 데이터 구조 (Python3) (tistory.com)