Software Engineer Encyclopedia
0%
Domain 01 · Computer Science & Programming Fundamentals · Pillar

Big-O والـ Amortized Analysis وSegment Tree وFenwick Tree

Complexity Analysis, Amortized Cost, Segment Trees and Fenwick Trees

إزاي تحسب التعقيد صح (worst/average/amortized، والـ hidden constants)، وليه List.Add بتاع .NET O(1) amortized، وإزاي Prefix sums وFenwick (BIT) وSegment trees بيجاوبوا range queries مع updates في O(log n) — بمسائل إنترفيو محلولة وتطبيقات في الـ backend.

  • Foundation
  • ~12 min read
  • 14 sections
  • 7 code examples
  • 3 diagrams
  • 6 questions
  • Priority L2 · Essential
  • C# 13 / .NET 10 · concepts language-independent

بعد الدرس ده هتقدر

  • تحسب Big-O لكود فيه loops متداخلة وrecursion (Master theorem بشكل عملي)
  • تفرق بين worst-case وaverage وamortized وتشرح amortized بـ aggregate وaccounting
  • تشرح ليه List.Add وDictionary resize amortized O(1) وتأثير ده على الـ latency
  • تستخدم prefix sums وdifference arrays للـ static ranges
  • تبني Fenwick tree للـ prefix sums مع point updates
  • تبني Segment tree للـ range sum/min/max ومع lazy propagation للـ range updates
  • تختار الهيكل الصح حسب نوع الـ queries والـ updates والقيود

المتطلبات قبل ما تبدأ

01

Big-O صح: إيه اللي بنقيسه فعلًا؟

What Big-O measures
Basics

Big-O بيوصف معدل نمو الوقت أو الذاكرة مع حجم الـ input، مش الوقت بالثواني. O(n) معناها «لو الـ input اتضاعف، الوقت تقريبًا بيتضاعف». ده بيخليك تتنبأ: الكود اللي شغال كويس على 1,000 عميل هيعمل إيه على مليون؟

التعقيدn = 10³n = 10⁶مثال
O(1)11Dictionary lookup (متوسط)
O(log n)~10~20binary search، B-tree index seek
O(n)10³10⁶scan، LINQ Where على List
O(n log n)~10⁴~2×10⁷sorting
O(n²)10⁶10¹² (ساعات)loop متداخل، N+1 queries على N عنصر

قواعد الحساب العملية

  • Loops متتالية بتتجمع: O(n) + O(m) = O(n + m). متداخلة بتتضرب: O(n × m).
  • بتتجاهل الثوابت والحدود الأصغر: 3n² + 100n = O(n²) — بس الثوابت بتفرق في الواقع (انظر تحت).
  • Recursion: عدد الاستدعاءات × الشغل في كل استدعاء. Merge sort: كل مستوى O(n)، وفيه log n مستوى ← O(n log n). الـ Master theorem بيعمم ده: T(n) = a·T(n/b) + f(n).
  • الـ hidden loops: list.Contains و list.IndexOf و string.Concat في loop و .Count() على IEnumerable كلها O(n) مستخبية.
C#spot the hidden O(n²)
// O(n^2): Contains on a List inside a loop
var result = new List<int>();
foreach (var id in incomingIds)                 // n
    if (!result.Contains(id)) result.Add(id);   // Contains is O(n) on List

// O(n): HashSet makes membership O(1) average
var seen = new HashSet<int>();
var unique = incomingIds.Where(seen.Add).ToList();   // Add returns false if already present
02

Worst مقابل average مقابل amortized

Three different guarantees
Deep dive
النوعبيقول إيهمثال
Worst caseضمان لكل عملية لوحدها، لأسوأ inputBinary search O(log n) دايمًا
Average (expected)متوسط على توزيع inputs أو randomnessHash table lookup O(1) متوسط، O(n) لو كل المفاتيح اتصادمت
Amortizedمتوسط على سلسلة عمليات، لأي سلسلة (مش احتمالي)List.Add: أغلب الإضافات O(1)، أحيانًا O(n) للـ resize، والمتوسط O(1)

ليه الفرق مهم في الـ backend؟ Amortized O(1) معناه إن عملية واحدة ممكن تاخد وقت طويل. في API بتبني List فيها مليون عنصر، الـ resize الأخير بينسخ نص مليون عنصر وبيعمل allocation كبيرة (ممكن تروح الـ Large Object Heap) ← spike في الـ p99 latency. لو عارف الحجم: new List<T>(capacity).

03

Amortized analysis بالحساب: الـ dynamic array

.Add is O(1) amortized" kind="deep">
capacity after each resize124816copies when growing to 16: 1 + 2 + 4 + 8 = 15 < 16n appends → n writes + < n copies → < 2n total → O(1) per append on average(.NET List<T> starts at 4 and doubles; the exact policy is an implementation detail)
Doubling capacity: copies happen rarely, و the total copy work stays below 2n

Aggregate method: مع مضاعفة السعة، الـ copies عند كل resize هي 1، 2، 4، …، n/2 — مجموعهم أقل من n. فـ n عملية Add كلها أقل من 2n شغل ← O(1) لكل واحدة في المتوسط.

Accounting method: اعتبر كل Add بيدفع 3 «عملات»: واحدة للكتابة، واتنين محوشين. لما الـ array يتملي ويتضاعف، العناصر اللي اتضافت من آخر resize محوشة كفاية لنسخ نفسها ونسخ عنصر قديم. الرصيد عمره ما بيبقى سالب ← التكلفة الـ amortized ثابتة.

ليه مش «+10 كل مرة»؟ لو السعة بتزيد بثابت، الـ copies = 10 + 20 + 30 + … = O(n²/10) ← O(n) لكل Add. المضاعفة (أو أي معامل > 1) هي اللي بتدّي O(1).

نفس التحليل بيشرح: Dictionary resize، StringBuilder، والـ queue المبني من stackين (كل عنصر بيتنقل مرة واحدة بالكتير).

04

لما الثوابت بتغلب الـ Big-O

Constants and memory locality
Practical
  • Cache locality: loop على int[] متتالي أسرع بكتير من linked list بنفس الـ O(n) لأن الـ CPU بيحمّل cache lines.
  • n صغير: linear search على 8 عناصر غالبًا أسرع من HashSet (حساب الـ hash + indirection).
  • I/O بيغلب كل حاجة: query واحدة للـ DB (~1ms) = ملايين عمليات في الذاكرة. N+1 queries مشكلة O(n) round-trips مش O(n) عمليات.
  • Allocations: LINQ chain على hot path بتعمل allocations بتضغط على الـ GC — نفس الـ O، تكلفة حقيقية أعلى. قيس بـ BenchmarkDotNet (Performance).
05

Range queries الثابتة: prefix sums و difference arrays

Static range queries
Practical

لو المصفوفة مش بتتغير، أي sum على [l, r] = prefix[r+1] − prefix[l] في O(1) بعد O(n) تجهيز.

C#prefix sums and a 2D version
long[] BuildPrefix(int[] a)
{
    var p = new long[a.Length + 1];
    for (int i = 0; i < a.Length; i++) p[i + 1] = p[i] + a[i];
    return p;
}
long RangeSum(long[] p, int l, int r) => p[r + 1] - p[l];      // inclusive [l, r]

// 2D: sum of a rectangle in O(1) after O(R*C) preprocessing (inclusion-exclusion)
// S(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Difference array (العكس): «زوّد x على كل العناصر من l لـ r» كتير، وبعدين اقرا النتيجة مرة: diff[l] += x; diff[r+1] −= x، وفي الآخر prefix sum على diff. ده مفيد مثلًا لحساب عدد الاشتراكات النشطة في كل يوم من فترات (start, end).

المشكلة: لو فيه updates بين الـ queries، prefix sums محتاجة O(n) لإعادة الحساب بعد كل update. هنا بييجي دور Fenwick و Segment trees.

06

Fenwick tree (BIT): prefix sums مع updates في O(log n)

Binary indexed tree
Deep dive

كل خانة tree[i] مسؤولة عن مجموع فترة طولها = أصغر bit مضاءة في i (i & −i). الـ prefix sum لحد i بيتجمع من O(log n) خانة بالنزول (i −= i & −i)، والـ update بيعدّل O(log n) خانة بالطلوع (i += i & −i).

t[1]: a1t[2]: a1..a2t[3]: a3t[4]: a1..a4t[5]: a5t[6]: a5..a6t[7]: a7t[8]: a1..a8prefix(7) = t[7] + t[6] + t[4] (7 → 6 → 4 → 0 by removing the lowest set bit)
Fenwick tree (1-indexed): each node covers a block whose size is its lowest set bit
C#Fenwick.cs
public sealed class Fenwick(int n)
{
    private readonly long[] _t = new long[n + 1];             // 1-indexed internally

    public void Add(int index, long delta)                     // 0-indexed public API
    {
        for (int i = index + 1; i < _t.Length; i += i & -i) _t[i] += delta;
    }
    public long Prefix(int count)                              // sum of the first `count` elements
    {
        long s = 0;
        for (int i = count; i > 0; i -= i & -i) s += _t[i];
        return s;
    }
    public long Range(int l, int r) => Prefix(r + 1) - Prefix(l);   // inclusive [l, r]
}

حدوده: Fenwick ممتاز للعمليات اللي ليها «عكس» (جمع وطرح). Range min/max مش بيتعمل بيه ببساطة لأن مفيش «طرح» للـ min. هنا الـ segment tree.

07

Segment tree: أي عملية associative على range

Segment trees
Deep dive

شجرة كل node فيها نتيجة العملية (sum/min/max/gcd) على فترة، والجذر على المصفوفة كلها، وكل node بيتقسم نصين. أي range [l, r] بيتغطى بـ O(log n) node، والـ point update بيعدّل مسار واحد من الورقة للجذر.

[0..7][0..3][4..7][0..1][2..3] ✓[4..5] ✓[6..7][6] ✓[7]query [2..6] = combine([2..3], [4..5], [6]) → O(log n) nodes
Segment tree over 8 elements: a query [2, 6] is answered by combining three nodes
C#SegmentTree.cs: iterative, range min with point updates
public sealed class MinSegmentTree
{
    private readonly int _n;
    private readonly int[] _t;
    public MinSegmentTree(int[] a)
    {
        _n = a.Length; _t = new int[2 * _n];
        Array.Copy(a, 0, _t, _n, _n);                                   // leaves at [n, 2n)
        for (int i = _n - 1; i > 0; i--) _t[i] = Math.Min(_t[2 * i], _t[2 * i + 1]);
    }
    public void Set(int index, int value)
    {
        int i = index + _n; _t[i] = value;
        for (i /= 2; i >= 1; i /= 2) _t[i] = Math.Min(_t[2 * i], _t[2 * i + 1]);
    }
    public int Min(int l, int r)                                         // inclusive [l, r]
    {
        int res = int.MaxValue;
        for (l += _n, r += _n + 1; l < r; l /= 2, r /= 2)
        {
            if ((l & 1) == 1) res = Math.Min(res, _t[l++]);
            if ((r & 1) == 1) res = Math.Min(res, _t[--r]);
        }
        return res;
    }
}

Lazy propagation: range updates

«زوّد 5 على كل العناصر من 100 لـ 90,000» كـ point updates = O(n log n). مع lazy propagation: لو node فترته كلها جوه الـ update، عدّل قيمته وسجّل «pending +5» عليه وما تنزلش لأولاده؛ ولما query أو update تانية تحتاج تنزل، ادفع الـ pending لأولاده الأول. النتيجة: range update و range query الاتنين O(log n).

08

أنماط amortized في مسائل الإنترفيو

Amortized patterns you will meet
Deep dive

تلات أنماط بتطلع كتير، وكلهم شكلهم O(n²) أو أسوأ لكن الـ amortized analysis بيثبت إنهم أسرع بكتير. السر في كل مرة: كل عنصر بيدخل ويخرج مرة واحدة بالكتير.

1) Monotonic stack: Next Greater Element

لكل عنصر، أول عنصر على يمينه أكبر منه. Brute force O(n²). بالـ stack: امشي من الشمال، وطول ما العنصر الحالي أكبر من الـ top، يبقى هو «الأكبر التالي» للـ top — pop وسجّل. فيه while جوه for، لكن كل index بيتعمله push مرة و pop مرة بالكتير ← 2n عملية ← O(n).

C#NextGreater.cs
public static int[] NextGreater(int[] a)
{
    var res = Enumerable.Repeat(-1, a.Length).ToArray();
    var stack = new Stack<int>();                         // indices with decreasing values
    for (int i = 0; i < a.Length; i++)
    {
        while (stack.Count > 0 && a[stack.Peek()] < a[i])
            res[stack.Pop()] = a[i];                       // each index is popped at most once
        stack.Push(i);
    }
    return res;
}
// Same idea: Daily Temperatures, Largest Rectangle in Histogram, stock span.

2) Monotonic deque: Sliding Window Maximum

أقصى قيمة في كل نافذة طولها k. Heap بيدّي O(n log k). Deque بيدّي O(n): احتفظ بـ indices قيمها تنازلية؛ اشيل من الآخر أي عنصر أصغر من الجديد (عمره ما هيبقى max تاني)، واشيل من الأول لو خرج من النافذة. الأول دايمًا هو الـ max.

C#SlidingWindowMax.cs
public static int[] MaxSlidingWindow(int[] a, int k)
{
    var dq = new LinkedList<int>();                        // indices, values decreasing from front to back
    var res = new int[a.Length - k + 1];
    for (int i = 0; i < a.Length; i++)
    {
        while (dq.Count > 0 && a[dq.Last!.Value] <= a[i]) dq.RemoveLast();
        dq.AddLast(i);
        if (dq.First!.Value <= i - k) dq.RemoveFirst();   // left the window
        if (i >= k - 1) res[i - k + 1] = a[dq.First.Value];
    }
    return res;
}

تطبيق مباشر: «أعلى latency في آخر 60 ثانية» لـ dashboard live من غير ما تخزن كل القيم مرتبة.

3) Union-Find بـ path compression و union by rank

Disjoint sets لـ «هل العنصرين في نفس المجموعة؟» مع دمج مستمر (connected components ديناميكيًا، تجميع حسابات مكررة، Kruskal). من غير تحسينات ممكن تبقى شجرة طويلة O(n). مع التحسينين، التكلفة الـ amortized لكل عملية O(α(n)) — α هي inverse Ackermann، ≤ 4 لأي n عملي، يعني ثابت فعليًا.

C#UnionFind.cs
public sealed class UnionFind
{
    private readonly int[] _parent, _rank;
    public UnionFind(int n) { _parent = Enumerable.Range(0, n).ToArray(); _rank = new int[n]; }

    public int Find(int x) => _parent[x] == x ? x : _parent[x] = Find(_parent[x]);   // path compression

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;
        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);                                // union by rank
        _parent[rb] = ra;
        if (_rank[ra] == _rank[rb]) _rank[ra]++;
        return true;
    }
}
// Real use: merging duplicate customer records that share an email OR a phone (entity resolution).
09

تمرين: احسب تعقيد الكود ده

Complexity drill
Practical
1: loop خارجي i من 1 لـ n، وداخلي j = i; j < n; j *= 2

الحل: الداخلي بيعمل حوالي log(n/i) خطوة. المجموع على i ≤ n log n ← O(n log n) (والتحليل الأدق بيدّي O(n)، لأن مجموع log(n/i) = O(n) — نقطة bonus لو قلتها).

2: recursion T(n) = 2T(n/2) + O(n)

الحل: log n مستوى، كل مستوى O(n) ← O(n log n) (merge sort). ولو T(n) = 2T(n/2) + O(1) ← O(n) (عدد الـ nodes في شجرة binary).

3: endpoint بيعمل foreach على orders وجواه await db.Customers.FindAsync(order.CustomerId)

الحل: O(n) queries للـ DB (N+1). من ناحية Big-O نفس الـ O(n)، لكن الثابت = round-trip شبكة لكل عنصر. الحل: query واحدة بـ join/Include أو WHERE Id IN (...) ← O(1) round-trips. ده المثال اللي بيوضح إن «عدد العمليات المكلفة» أهم من «عدد العمليات».

10

تختار إيه؟

Choosing the structure
Basics
الموقفالهيكلQueryUpdate
بيانات ثابتة، range sumsPrefix sumsO(1)O(n)
Range updates كتير ثم قراءة مرةDifference arrayO(n) مرة واحدةO(1)
Prefix/range sums + point updatesFenwickO(log n)O(log n)
Range min/max/gcd + updatesSegment treeO(log n)O(log n)
Range updates + range queriesSegment tree + lazyO(log n)O(log n)
Static range min (بدون updates)Sparse tableO(1)—

في الـ backend الحقيقي: نادرًا هتكتب segment tree بإيدك — الـ database بيعمل aggregations و indexes. لكن الأفكار بتظهر: time-series rollups (pre-aggregated buckets = prefix-like)، rate limiters بـ sliding windows (عدّادات لكل segment زمني)، و leaderboards (Redis sorted sets = skip list بـ O(log n)). ولو عندك in-memory analytics على ملايين النقط بتتحدث، Fenwick هو أبسط حل صحيح.

11

أخطاء شائعة

Common mistakes
Basics
  • اعتبار O(1) average ضمان: hash flooding (مفاتيح مصممة تتصادم) بيحوّل الـ Dictionary لـ O(n) — ‎.NET بيستخدم randomized string hashing للحماية.
  • نسيان تكلفة الـ resize في الـ hot path: pre-size الـ collections لما الحجم معروف.
  • Off-by-one في Fenwick (1-indexed جوه، 0-indexed برّه) — اعزل التحويل في الـ public API زي فوق.
  • Segment tree بحجم 2n مع n مش power of 2 في implementations الـ recursive (محتاجة 4n)، أو overflow في الـ sums (استخدم long).
  • بناء هيكل معقد لما الـ database ممكن تعمل الـ query بـ index مناسب.
12

اختبر فهمك

Knowledge check
Basics

محتاج range minimum مع point updates على 10⁶ عنصر و10⁵ query. الأنسب؟

كود فيه loop على n عنصر وجواه list.Contains على list بتكبر لحد n. التعقيد؟

13

مسائل إنترفيو محلولة

Interview problems with reasoning
Practical
1 (Easy→Medium): Range Sum Query — Immutable ثم Mutable

Immutable: prefix sums ← O(1) لكل query. Mutable (المحاور ضاف update): prefix sums هتبقى O(n) لكل update. قول الـ trade-off بصوت عالي، وبعدين Fenwick: update و query O(log n). لاحظ إن update في المسألة غالبًا «set value» مش «add» ← احسب الفرق delta = new − old واحتفظ بنسخة من المصفوفة.

2 (Medium): Count of Smaller Numbers After Self

التفكير: Brute force O(n²). امشي من اليمين للشمال، ولكل رقم اسأل «كام رقم أصغر مني شفته؟» = prefix count على القيم. اعمل coordinate compression للقيم (رتّبهم وخد rank)، و Fenwick على الـ ranks: query(rank − 1) ثم add(rank, 1). O(n log n). نفس الفكرة بتحسب عدد الـ inversions.

3 (Medium): Car Pooling / حجوزات — هل السعة اتعدت في أي لحظة؟

التفكير: كل رحلة = +passengers عند البداية، −passengers عند النهاية = difference array على الزمن، وبعدين prefix sum وتأكد إن مفيش لحظة تعدت السعة. O(n + T). لو الأوقات كبيرة جدًا: رتّب الأحداث (sweep line) ← O(n log n). ده نفس منطق «أقصى عدد sessions متزامنة» في الـ analytics.

4 (Senior discussion): leaderboard لمليون لاعب، تحديث score كل ثانية، وطلب «ترتيبي كام؟»

التفكير: sorted list = O(n) لكل update. الخيارات: Redis sorted set (ZADD/ZREVRANK في O(log n)، الأبسط تشغيليًا)، أو Fenwick على buckets الـ scores لو الـ scores أعداد صحيحة في نطاق محدود (rank = عدد اللي score أعلى = suffix count). ناقش الـ sharding (leaderboard لكل منطقة + global تقريبي)، و consistency (ترتيب بتأخير ثانية مقبول؟).

14

أسئلة إنترفيو

Interview questions
Basics
(Junior) إيه معنى amortized O(1)؟
إن متوسط تكلفة العملية على أي سلسلة طويلة من العمليات ثابت، حتى لو عمليات قليلة بعينها مكلفة (زي resize الـ List). مش متوسط احتمالي — ضمان على السلسلة.
(Mid) ليه Dictionary ممكن يبقى O(n) في lookup؟
لو مفاتيح كتير ليها نفس الـ hash bucket (hash ضعيف أو مفاتيح عدائية)، الـ bucket بيبقى قائمة طويلة. الحماية: GetHashCode كويس، و randomized hashing للـ strings (موجود في ‎.NET).
(Senior) API بيحسب «أعلى 10 منتجات مبيعًا في آخر ساعة» في كل request وبطيء. تصميمك؟
pre-aggregation في buckets دقيقة (عدّاد لكل منتج لكل دقيقة في Redis/hash)، sliding window = مجموع آخر 60 bucket، و top-k بـ heap بحجم 10، والنتيجة نفسها في cache لثواني. لو الدقة المطلقة مش لازمة: Count-Min Sketch + heap. والـ trade-off بين freshness والتكلفة واضح للـ product.
↗

المراجع والقراءة الإضافية

References & further reading

الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)

خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.

محتويات الدرس