F1. Tree Cutting (Easy Version
F1. Tree Cutting (Easy Version)
Topic: DFS
Concept: প্রতিটা প্যারেন্ট এর চাইল্ড কোন কোন কালার আছে তার হিসাব রাখবো, যেমন প্রথম উদাহরনে -
১ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ২টা নীল , ১টা নরমাল।
২ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল, ১টা নীল , ২টা নরমাল।
৩ নং এর ১টা নরমাল (নিজের কালার)।
৪ নং নোডের চাইল্ড এর সংখ্যা হবে ১টা লাল ( এইটা বাদ দিয়ে এন্সার পাব)।
৫ নং নোডের চাইল্ড এর সংখ্যা হবে 1টা নীল।
Solution 01:
Segment Tree
Resource Link:
টিউটোরিয়াল গুলো ক্রম অনুযায়ী সাজানো নাই।
ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১
ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-২ (লেজি প্রপাগেশন)
Kaidul blog
blog
Segment tree/ BIT part - 1
লোয়েস্ট কমন অ্যানসেস্টর
Persistent Segment Tree (Part - 01)
Persistent Segment Tree (Part - 02)
A simple approach to segment trees
A simple approach to segment trees, part 2
TopCoder Tutorial
Indian Computing Olympiad
visualgo
E-Maxx : Segment Tree
Algorithm Gym :: Everything About Segment Trees
Efficient and easy segment trees
Segment trees (for beginners)
csacademy
Segment Trees and lazy propagation
Segment Trees
Persistent segment trees – Explained with spoj problems
Persistence Made Simple - Tutorial
CF blog problem list
Problem Link
CF blog problem list
Lazy Segment tree
Bucket Sort
Bucket Sort
geeksforgeeks
hackerearth
visualization
Time Complexity: If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time. The O(1) is easily possible if we use a linked list to represent a bucket (In the following code, C++ vector is used for simplicity). Step 4 also takes O(n) time as there will be n items in all buckets.