Subarray Sum Queries (CSES) | Segment Tree (Dynamic Kadane’s Algorithm)

In this video, we solve the 𝐒𝐮𝐛𝐚𝐫𝐫𝐚𝐲 𝐒𝐮𝐦 𝐐𝐮𝐞𝐫𝐢𝐞𝐬 problem from the CSES Problem Set.⁣⁣⁣
⁣⁣⁣
We start with an array and then process a series of point updates. After each update, we need to find the maximum subarray sum of the entire array. Empty subarrays are allowed, which means the answer can never be negative.⁣⁣⁣
⁣⁣⁣
This is essentially 𝐊𝐚𝐝𝐚𝐧𝐞’𝐬 𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 𝐛𝐮𝐭 𝐞𝐱𝐭𝐞𝐧𝐝𝐞𝐝 𝐰𝐢𝐭𝐡 𝐮𝐩𝐝𝐚𝐭𝐞𝐬 — so we can’t just run Kadane every time. Instead, we build a Segment Tree that stores four values for each segment:⁣⁣⁣
⁣⁣⁣
- Total sum of the segment⁣⁣⁣
- Best prefix sum⁣⁣⁣
- Best suffix sum⁣⁣⁣
- Best subarray sum⁣⁣⁣
⁣⁣⁣
With these, we can merge results in O(1) per node, giving us efficient O(log n) updates.⁣⁣⁣
⁣⁣⁣
👉 𝐊𝐞𝐲 𝐜𝐨𝐧𝐜𝐞𝐩𝐭𝐬 𝐜𝐨𝐯𝐞𝐫𝐞𝐝 𝐢𝐧 𝐭𝐡𝐢𝐬 𝐯𝐢𝐝𝐞𝐨:⁣⁣⁣
⁣⁣⁣
- Recap of Kadane’s Algorithm⁣⁣⁣
- Extending Kadane to work with updates⁣⁣⁣
- Designing a Segment Tree for max subarray sum⁣⁣⁣
- Handling updates in O(log n)⁣⁣⁣
- Why the final answer must be max(0, best_subarray_sum)⁣⁣⁣
⁣⁣⁣⁣⁣⁣
📌 Watch this till the end to fully understand the intuition, not just the code.⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👉 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐋𝐢𝐧𝐤: https://cses.fi/problemset/task/1190⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👉 𝐖𝐚𝐭𝐜𝐡 𝐭𝐡𝐞 𝐟𝐮𝐥𝐥 𝐩𝐥𝐚𝐲𝐥𝐢𝐬𝐭 𝐡𝐞𝐫𝐞: https://youtube.com/playlist?list=PLtfqa971vD5GTQjH9U0H6kiq9cQlFFa5k&si=YKuHrjhvmUlXoTBM⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👉 Whether you are a beginner or looking to strengthen your problem-solving skills, this course will help you 𝐭𝐡𝐢𝐧𝐤 𝐥𝐢𝐤𝐞 𝐚 𝐜𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐞𝐫 𝐚𝐧𝐝 𝐚𝐩𝐩𝐥𝐲 𝐬𝐞𝐠𝐦𝐞𝐧𝐭 𝐭𝐫𝐞𝐞 𝐜𝐨𝐧𝐟𝐢𝐝𝐞𝐧𝐭𝐥𝐲 𝐢𝐧 𝐜𝐨𝐧𝐭𝐞𝐬𝐭𝐬.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👋 𝐖𝐞𝐥𝐜𝐨𝐦𝐞 𝐭𝐨 𝐭𝐡𝐞 𝐜𝐡𝐚𝐧𝐧𝐞𝐥!⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
I create content on 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠, 𝐃𝐚𝐭𝐚 𝐒𝐭𝐫𝐮𝐜𝐭𝐮𝐫𝐞𝐬 & 𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦𝐬 (𝐃𝐒𝐀), 𝐚𝐧𝐝 𝐓𝐞𝐜𝐡𝐧𝐢𝐜𝐚𝐥 𝐈𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐏𝐫𝐞𝐩𝐚𝐫𝐚𝐭𝐢𝐨𝐧.⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
If you find this video helpful, don’t forget to:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
👍 Like the video⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
💬 Comment your doubts/questions (I reply to everyone!)⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🔔 Subscribe and turn on notifications to never miss upcoming tutorials⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
📌 Connect with me:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🐦 X: https://x.com/Yash_Poonia_⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
💼 LinkedIn: https://www.linkedin.com/in/yashpoonia/⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
💻 GitHub: https://github.com/yash7xm⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣
🌐 Discord: https://discord.gg/cYeENy6C⁣⁣⁣⁣⁣⁣⁣⁣
⁣⁣⁣⁣⁣⁣⁣⁣
#CSES #CompetitiveProgramming #SegmentTree #Kadane #DSA #Coding #Algorithms

Видео Subarray Sum Queries (CSES) | Segment Tree (Dynamic Kadane’s Algorithm) канала Yash Poonia