Contact Form Submission - Request - Missing Section or Solution (Advanced - Persistent Data Structures)

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/adv/persistent?lang=cpp Module: Advanced - Persistent Data Structures Topic: Request - Missing Section or Solution Message: There should be an explanation of what a persistent data structure is to begin with, and some of the details of what the update/query are actually supposed to do.

[DinosaurPotato534]

I'll try to fix. If there's anything specific I should know before diving in let me know.

[ghost]

For the Fat Nodes code in C++ under Persistent Arrays, here is a solution in Python:

def get_item(index, time):
    # Gets the array item at a given index and time
    ub = next((x for x in arr[index] if x[0] > time), None)
    if ub is not None:
        return ub[1]
    return arr[index][-1][1]

def update_item(index, value, time):
    # Updates the array item at a given index and time
    # Note that this only works if the time is later than all previous
    # update times
    assert arr[index][-1][0] < time
    arr[index].append([time, value])

def init_arr(n, init):
    # Initializes the persistent array, given an input array
    for i in range(n):
        arr[i].append([0, init[i]])```