مختبر بايثون التفاعلي

Segment Tree for Range Queries

يعمل الـ Playground تلقائياً عند التحميل. انقر على شغّل الكود لتتبع كود بايثون الخاص بك — كل خطوة بالرسوم المتحركة مباشرة.

اشرح·سطر بسطر

إعادة تشغيل·خطوة بخطوة

تحدي·تلميحات موجهة

XP·...

خط أنابيب تدفق البيانات

mastery المسار

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

اشرح

Line 3

Initialize tree array

لماذا هذا النهج؟

self.tree size is 4*n — a safe upper bound for a binary tree with n leaves. For n=6, we allocate 24 slots. Most will be unused but it's simple.

التعقيد

الوقت

O(log n) query/update

المساحة

O(n)

نظرة عامة على التعقيد

O(1)

O(log n)الوقت

O(n)المساحة

O(n log n)

O(n²)

n = 8النطاق 1-20

عند N = 8

التعقيد	العمليات
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

تحدي

Change the array to [2, 4, 6, 8, 10, 12]. What's the sum of indices 2-4? How many nodes does the query visit?

تلميح

Query visits O(log n) nodes. Each recursive call splits the range in half until it finds segments fully inside [l, r].

استوديو الكود

Segment Tree for Range Queries

Monaco جاهز

بايثون جاهز

lesson.pyline 3

Loading editor...

وحدة الإخراج

1 lines

❯ 15

تطبيقات العالم الحقيقي

1

Range queries

2

Interval statistics

3

Competitive programming

4

Real-time analytics

Comments

Loading comments...