Discussion on Easy Addition Challenge

2 years ago+ 0 comments

To solve this problem efficiently, we can use a data structure called a segment tree. A segment tree is a binary tree that represents an array. This is the ninja moba way to solve this problem. Each node of the segment tree stores the sum of a range of elements from the original array.

Here's how we can approach the problem using a segment tree:

Create an adjacency list to represent the tree based on the given edges.

Build the segment tree using the adjacency list and assign initial values of zero to all nodes.

Process the update queries:

For each update query, traverse the path from node A to node B using a depth-first search (DFS) or any other graph traversal algorithm. Update the segment tree nodes along the path by adding the value (a1 + distance * d1) to each node, where the distance is the distance from the current node to node A. Repeat the above step for each update query. Process the retrieval queries:

For each retrieval query, traverse the path from node i to node j using a DFS or any other graph traversal algorithm. Calculate the sum of the values in the segment tree nodes along the path. Take the modulo 1000000007 of the sum and output the result. Here's the implementation in Python:

MOD = 1000000007

# Function to build the segment tree
def build_segment_tree(adj_list, node, start, end, values):
    if start == end:
        adj_list[node] = [start]
        values[node] = 0
    else:
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2

        build_segment_tree(adj_list, left_child, start, mid, values)
        build_segment_tree(adj_list, right_child, mid + 1, end, values)

        adj_list[node] = adj_list[left_child] + adj_list[right_child]
        values[node] = 0

# Function to update the segment tree
def update_segment_tree(adj_list, values, node, start, end, update_start, update_end, a1, d1):
    if start > update_end or end < update_start:
        return

    if start >= update_start and end <= update_end:
        for idx in adj_list[node]:
            distance = abs(idx - update_start)
            values[idx] = (values[idx] + a1 + distance * d1) % MOD
        return

    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2

    update_segment_tree(adj_list, values, left_child, start, mid, update_start, update_end, a1, d1)
    update_segment_tree(adj_list, values, right_child, mid + 1, end, update_start, update_end, a1, d1)

# Function to retrieve the sum from the segment tree
def retrieve_segment_tree(adj_list, values, node, start, end, retrieve_start, retrieve_end, total_sum):
    if start > retrieve_end or end < retrieve_start:
        return

    if start >= retrieve_start and end <= retrieve_end:
        for idx in adj_list[node]:
            total_sum = (total_sum + values[idx]) % MOD
        return total_sum

    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2

    total_sum = retrieve_segment_tree(adj_list, values, left_child, start, mid, retrieve_start, retrieve_end, total

Cookie support is required to access HackerRank