Help needed in approach ( Need Video Resource)

I need a video lecture for this type of question-

Que1 : “Uni queries | Practice Problems
Que2 : “Courses - Codeforces

we have to add some value in each node of a particular set , and after that print the value of the particular node this type of questions ,i wanna do , but don’t know aporach so can u please tell the resource or approach in detailed manner.

@galencolin @everule1 @ssjgz @carre @tamo11

I tried a similar approach in both the places, and both of them passed, so I think you can use this-

  1. Joining
  • Let us take 2 components with root nodes x and y, and find the size of the components. It is obvious to add the smaller component to the larger component. Say x is root of larger component.
  • We will mark x as the parent node of all the nodes we are adding.
  • For every node, we will make the following updates-
    update all the pending additions for the component in which it previously belonged
    subtract the pending additions for the component to which it it will belong now (why? you will see below)
  1. Updating
    Just add the value to the pending list of updates for the component it belongs to.
  2. Query
    For the given node, answer will be equal to sum of value at current node and updates pending for the given component
    Now suppose we updated a component, added another component to it and then updated again.
    The first update isn’t valid for the elements of the newly added component, but the next one is. So when we add the entire sum of pending updates, some unnecessary additions happen too. To prevent this, we subtract the pending additions before adding it to the component.

The updating and query time complexity will be O(1), and the joining time complexity will be O(nlogn) in worst case.
A spaghetti code here which probably wont help much I guess.

For the codeforces problem:

  • try to use a extra array to keep track of the updated values of the entire component via the head node. The starting index for the updated value should be saved in the child nodes.

  • When you do a join operation, simply add a extra position to the dynamic value array and update the index of the valuelist of the head to the child. Suppose you are joining two parents A and B. And suppose A is to be the head then add a 0 to the valuelist of the head and update the index position of B to be 1. Remember the value of the index of the head is always -1. Since it is not linked to any parent.

  • Whenever you are doing path compression, go to the parent of the current node and update the value of this node by applying prefix sum on the arraylist that then go to the parent of the parent and then update both the child nodes and continue the process till the head node.

  • By using prefix sum on the array that stores the updated values that you are adding each time to the component, you optimize the time complexity to O(1).

The java implementation code is:

    package Codeforces.ITMO_PilotCourse.DisjointSetUnion.Step1;

import java.util.*;
public class C{
    static class Set{
        int id;
        int count;
        int value;
        Set parent;
        int index;
        ArrayList<Integer> valuelist;
        Set(int id)
        {
            this.id = id;
            this.parent = this;
            this.value = 0;
            this.valuelist = new ArrayList<>();
            this.index = -1;
            this.count = 1;
        }
        public Set getParent()
        {
            //If the player is the head of the set itself then return the parent
            if(this.parent==this)
            {
                return this;
            }

            //If the parent of the player is the head of the set
            if(this.parent.parent == this.parent)
            {
                //Add the due value of this player at the last of its valuelist as per prefixSum
                if(this.valuelist.size()==0)
                    this.valuelist.add(this.parent.getSum(this.index));
                else this.valuelist.add(this.parent.getSum(this.index) + this.valuelist.get(this.valuelist.size()-1));

                //Also update the value of this player
                this.value += this.parent.getSum(this.index);

                //Add a new value which will be the new index value
                if(this.parent.valuelist.size()==0)
                    this.parent.valuelist.add(0);
                else this.parent.valuelist.add(this.parent.valuelist.get(this.parent.valuelist.size()-1));

                //So update the this players index
                this.index = this.parent.valuelist.size()-1;

                return this.parent;
            }


            Set parent = this.parent.getParent();

            //Add the due value of this player
            if(this.valuelist.size()==0)
                this.valuelist.add(this.parent.getSum(this.index));
            else this.valuelist.add(this.parent.getSum(this.index) + this.valuelist.get(this.valuelist.size()-1));

            //Update the due value
            this.value += this.parent.getSum(this.index);
            //Update the index
            this.index = this.parent.index;
            //Update the parent
            this.parent = parent;
            return parent;
        }
        public int getSum(int index)
        {
            if(this.valuelist.size()==0)
                return 0;
            else if(index==0)
                return this.valuelist.get(this.valuelist.size()-1);
            else return this.valuelist.get(this.valuelist.size()-1) - this.valuelist.get(index-1);
        }
        public void addValue(int value)
        {
            if(this.valuelist.size()==0)
                this.valuelist.add(value);
            else this.valuelist.set(this.valuelist.size()-1,
                    value+this.valuelist.get(this.valuelist.size()-1));

            this.value += value;
        }
        public void union(Set parent2)
        {
            if(this.count>parent2.count)
            {
                parent2.parent = this;
                //Add a new value which will be the new index value
                if(this.valuelist.size()==0)
                    this.valuelist.add(0);
                else this.valuelist.add(this.valuelist.get(this.valuelist.size()-1));

                parent2.index = this.valuelist.size()-1;
                this.count += parent2.count;
            }
            else
            {
                this.parent = parent2;

                if(parent2.valuelist.size()==0)
                    parent2.valuelist.add(0);
                else parent2.valuelist.add(parent2.valuelist.get(parent2.valuelist.size()-1));

                this.index = parent2.valuelist.size()-1;
                parent2.count += this.count;
            }
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Set[] players = new Set[n];
        for(int i=0;i<n;i++)
        {
            players[i] = new Set(i);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<m;i++)
        {
            String type = sc.next();
            if(type.equals("join"))
            {
                int player1 = sc.nextInt()-1;
                int player2 = sc.nextInt()-1;

                Set parent1 = players[player1].getParent();
                Set parent2 = players[player2].getParent();
                if(parent1!=parent2)
                {
                    parent1.union(parent2);
                }
            }
            else if(type.equals("add"))
            {
                int player1 = sc.nextInt()-1;
                int value = sc.nextInt();
                Set parent1 = players[player1].getParent();

                parent1.addValue(value);
            }
            else {
                int player1 = sc.nextInt()-1;
                players[player1].getParent();
                sb.append(players[player1].value).append("\n");
            }
        }

        System.out.println(sb);
    }
}