🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Segment Tree and Fenwick Tree: all 10 questions

Quiz: Segment Tree and Fenwick Tree · Question 8 of 10

What does this print? (code)

What does this print?

n = 8
T = [0] * (n + 1)
def add(i, x):
    while i <= n:
        T[i] += x
        i += i & -i
def prefix(i):
    s = 0
    while i > 0:
        s += T[i]
        i -= i & -i
    return s
for i, v in enumerate([3, 1, 4, 1, 5, 9, 2, 6], start=1):
    add(i, v)
print(prefix(4), prefix(8) - prefix(5))
  1. A.9 17
  2. B.9 22
  3. C.14 17
  4. D.8 17
Answer & explanation

Correct answer: 9 17

prefix(4) = 3 + 1 + 4 + 1 = 9; positions 6 to 8 hold 9 + 2 + 6 = 17.

Can you get the rest right without peeking?

Take the timed Quiz: Segment Tree and Fenwick Tree quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →