أشجار المقاطعSegment Trees

Segment tree هي هيكل بيانات تسمح بمعالجة استعلامات النطاق والتحديثات على المصفوفات بكفاءة.

في هذا القسم، يُفترض أن مواقع عناصر المصفوفة ونطاقات الاستعلام مرقمة ابتداءً من 1 ما لم يُذكر خلاف ذلك.

لاحقًا، عند كتابة segment tree بلغة C++، سنخزن المصفوفة الأصلية a بترقيم يبدأ من 0 كالمعتاد في C++، بينما ستبقى المواقع المستخدمة في الاستعلامات والتحديثات مرقمة ابتداءً من 1.

ما هي `Segment Tree`؟

هي شجرة ثنائية حيث يمثل كل node إجابة استعلام على مقطع (مصفوفة جزئية) من المصفوفة الأصلية. يتم بناء الشجرة وفق القواعد التالية:

كل leaf node يمثل مقطعًا بطول \(1\).
كل internal node يمثل دمجًا (sum, min, max, etc.) لطفليه.

لنفترض أن لدينا المصفوفة [2, 4, 6, 8]. فإن Segment Tree تحسب جمعًا لنطاقات مبنية على هذه المصفوفة تكون كما يلي:

graph TD
    A["20 (1-4)"]
    B["6 (1-2)"]
    C["14 (3-4)"]
    D["2 (1-1)"]
    E["4 (2-2)"]
    F["6 (3-3)"]
    G["8 (4-4)"]
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

لاحظ أن جميع الـleaf nodes تمثل عنصرًا واحدًا فقط، بينما تقوم بقية الـnodes بدمج طفليها بأخذ مجموع قيمتيهما.

عدد الـnodes والحشو

ليكن N عدد الـleaf nodes في segment tree بعد الحشو، وn طول المصفوفة الأصلية.

عدد الـnodes

في segment tree مكتملة، يشكل عدد الـnodes في كل مستوى المتتالية [1, 2, 4, …]، أي قوى العدد اثنين.
كل قوة للعدد 2 تساوي مجموع جميع القوى السابقة للعدد 2 زائد 1.
لذلك، إذا كان للشجرة N من الـleaf nodes، فإن العدد الكلي للـnodes هو 2N - 1.

لاحقًا، عند تخزين الشجرة في مصفوفة، سنحجز عادةً 2N موضعًا لأن الموضع 0 لن يُستخدم. أما الـnodes الفعلية للشجرة فتشغل المواقع من 1 إلى 2N - 1.

الحشو

إذا كانت المصفوفة الأصلية تحتوي على n عنصرًا وn ليست قوة للعدد اثنين، نقوم بحشو المصفوفة بعناصر إضافية بحيث يصبح عدد الـleaf nodes N هو القوة التالية للعدد اثنين. ويجب اختيار قيم الحشو بحيث لا تؤثر على قيم الـnodes الأخرى.
في أسوأ الحالات، نحتاج إلى إضافة أقل من n عناصر، لأن القوة التالية للعدد اثنين أصغر تمامًا من 2n. لذلك فإن أكبر عدد ممكن من عناصر الحشو هو n - 1.

مثال

إذا غيرنا المثال السابق إلى [2, 4, 6]، فنحتاج إلى إضافة عنصر لجعل الطول قوة للعدد اثنين دون التأثير على القيم الأخرى. أفضل قيمة لإضافتها في هذه الحالة هي 0، لأنها لا تغير المجاميع. ستكون segment tree الناتجة كما يلي:

graph TD
    A["12 (1-4)"]
    B["6 (1-2)"]
    C["6 (3-4)"]
    D["2 (1-1)"]
    E["4 (2-2)"]
    F["6 (3-3)"]
    G["0 (4-4) مضافة"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

التمثيل

سنمثل الـsegment tree كمصفوفة، بحيث نعطي موقعًا لكل node. وبالتالي سيتم إعطاء المواقع للـsegment tree السابقة كما يلي:

graph TD
    A["1: sum = 12 (1-4)"]
    B["2: sum = 6 (1-2)"]
    C["3: sum = 6 (3-4)"]
    D["4: sum = 2 (1-1)"]
    E["5: sum = 4 (2-2)"]
    F["6: sum = 6 (3-3)"]
    G["7: sum = 0 (4-4) مضاف"]
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

كل node i لها طفلان في الموضعين 2 * i و2 * i + 1، ووالدها في الموضع i / 2.

في هذا المثال، عدد الـleaf nodes N هو 4، وهو أيضًا موقع أول leaf node. لذلك فإن الـleaf node الموجودة في الموضع i في الـsegment tree تقابل الموقع المرقم ابتداءً من 1 i - N + 1 في المصفوفة الأصلية.

وبشكل مكافئ، فإن الموقع j في المصفوفة الأصلية يقابل الموضع التالي في الـsegment tree:

j + N - 1

فمثلًا، الموقع 1 من المصفوفة الأصلية يُخزن في seg[N].

الاستعلام

لنعرّف الدالة query(id, l, r, ql, qr) التي تقوم بحساب ناتج استعلام من ql إلى qr، حيث:

id هو موقع الـnode الحالي.
l هو بداية النطاق الذي يغطيه الـnode الحالي.
r هو نهاية النطاق الذي يغطيه الـnode الحالي.
ql هو بداية نطاق الاستعلام.
qr هو نهاية نطاق الاستعلام.

جميع القيم l وr وql وqr تمثل مواقع مرقمة ابتداءً من 1.

تعمل الدالة كما يلي:

إذا كان المجالان [ql, qr] و[l, r] غير متقاطعين تمامًا، يتم تجاهل الـnode الحالي لأنه لا يسهم في الاستعلام.
إذا كان المجال [ql, qr] يغطي بالكامل المجال [l, r]، نقوم بإرجاع القيمة المخزنة في الـnode الحالي.
خلاف ذلك، نقسم المجال عند المنتصف m = (l + r) / 2 ونقوم بالاستدعاء الذاتي على الطفلين:
- query(2 * id, l, m, ql, qr)
- query(2 * id + 1, m + 1, r, ql, qr)
ثم ندمج النتائج للحصول على إجابة الـnode الحالي.

لحل استعلام [ql, qr] نستدعي query(1, 1, N, ql, qr).

تعقيد الزمن لهذه الخوارزمية هو \(O(\log n)\).

تحديث نقطة

بعض المسائل تطلب تحديث القيمة عند الموقع j المرقم ابتداءً من 1 إلى القيمة v.

الـleaf node التي تقابل الموقع j مخزنة في:

j + N - 1

لذلك نقوم بتحديث الـleaf node في الموضع j + N - 1 ثم نعيد حساب قيم جميع آبائها.

عدد الآباء يساوي ارتفاع الشجرة، أي \(\log_2 N\). وبما أن N لا تتجاوز القوة التالية للعدد اثنين بعد n، فإن تعقيد تحديث النقطة هو \(O(\log n)\).

طريقة الكتابة

عند بناء segment tree لدينا المصفوفة الأصلية a، وهي مصفوفة C++ مرقمة ابتداءً من 0، وحجمها n.

أما الـsegment tree نفسها فسنخزن الـnodes فيها بترقيم يبدأ من 1:

seg[1] هي جذر الشجرة.
طفلا seg[i] هما seg[2 * i] وseg[2 * i + 1].
seg[0] غير مستخدمة.

كما أن المواقع المستخدمة في الاستعلامات والتحديثات مرقمة ابتداءً من 1. لذلك:

الموقع j في المصفوفة يقابل a[j - 1].
الموقع j في المصفوفة يقابل الـleaf node seg[j + N - 1].

حجم الشجرة

أولًا نحتاج إلى حساب عدد الـleaf nodes N، وهو أصغر قوة للعدد اثنين لا تقل عن n. نجده بالبدء من 1 ومضاعفته حتى يصبح كبيرًا بما يكفي:

int N = 1;
while (N < n) {
    N *= 2;
}

مثلًا، إذا كانت n تساوي 5 فإن الحلقة تعطي N = 8، وإذا كانت n قوة للعدد اثنين أصلًا فإن الحلقة تتوقف فورًا وتبقى N مساوية لـn.

نحتاج إلى 2*N موضعًا في المصفوفة. وبما أن N تُحسب أثناء تشغيل البرنامج هنا، فيمكننا استخدام vector:

vector<int> seg(2 * N);

رغم أن الشجرة تحتوي فعليًا على 2N - 1 من الـnodes، فإن الموضع 0 غير مستخدم، ولذلك يجب أن تكون المواقع من 1 إلى 2N - 1 متاحة.

بناء `segment tree`

سنكتب الكود لبناء segment tree تحسب المجموع.

بناء الـleaf nodes

لبناء الشجرة نضع أولًا قيم الـleaf nodes.

المصفوفة الأصلية a مرقمة ابتداءً من 0، لذلك فإن a[i] تمثل الموقع المرقم ابتداءً من 1 i + 1. ويتم تخزين هذا الموقع عند الموضع N + i في الـsegment tree.

for (int i = 0; i < n; i++) {
    seg[i + N] = a[i];
}

ثم نقوم بحشو العناصر الجديدة لإكمال الـleaf nodes.

for (int i = n + N; i < 2*N; i++) {
    seg[i] = 0;  // segment treeالقيم المضافة تعتمد على نوع ال
}

بناء الـinternal nodes

لبناء الـinternal nodes نمر عليها بترتيب عكسي ونقوم بدمج طفلي كل internal node.

for (int i = N - 1; i > 0; i--) {
    seg[i] = seg[i * 2] + seg[i * 2 + 1];  // دمج قيم الطفلين
}

الاستعلامات

الموقعان ql وqr، بالإضافة إلى حدود مجال الـnode l وr، كلها مرقمة ابتداءً من 1.

int query(int id, int l, int r, int ql, int qr) {
    // تأكد إذا لا يتقاطعان
    if (ql > r || l > qr) {
        return 0;
    }
    // بالكامل [l, r] يشمل [ql, qr] تأكد إذا
    if (ql <= l && r <= qr) {
        return seg[id];
    }
    // قم بالاستدعاء الذاتي والدمج
    int m = (l + r) / 2;
    return query(id * 2, l, m, ql, qr) + query(id * 2 + 1, m + 1, r, ql, qr);
}

لاستعلام المجال المرقم ابتداءً من 1 [ql, qr] نستخدم:

query(1, 1, N, ql, qr);

تحديث الـleaf node

هنا j هو موقع في المصفوفة مرقم ابتداءً من 1. وبما أن a مخزنة كمصفوفة C++ عادية مرقمة ابتداءً من 0، فإن الموقع j يقابل a[j - 1].

أما الـleaf node المقابلة له في الـsegment tree فهي j + N - 1.

void pointUpdate(int j, int v) {
    a[j - 1] = v;

    int idx = j + N - 1;
    seg[idx] = v;

    // أعد بناء جميع الآباء
    for (int i = idx / 2; i > 0; i /= 2) {
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    }
}

مثال على مسألة

Dynamic Range Minimum Queries

CSES easy

لديك المصفوفة \(x\) المكونة من \(n\) عنصر و\(q\) استعلامات. كل استعلام يكون من أحد النوعين:

“1 \(k\) \(u\)”: تحديث القيمة في الموضع \(k\) إلى \(u\).
“2 \(a\) \(b\)”: ما هي أصغر قيمة في المجال [\(a\),\(b\)]؟

الحل

سنقوم ببناء segment tree للقيمة الصغرى ونطبق الاستعلامات وتحديثات النقاط مباشرة عليها. وبما أن الشجرة هي segment tree للقيمة الصغرى، فستوجد بعض الاختلافات عن المقاطع البرمجية السابقة: فبدلًا من جمع قيم الطفلين، نأخذ القيمة الصغرى بينهما، كما أن القيمة المحايدة المستخدمة في الحشو وعند عدم تقاطع نطاق الاستعلام هي INT_MAX بدلًا من 0.

#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 200000;
const int N = 262144;  // أصغر قوة للعدد اثنين لا تقل عن MAXN

int seg[N * 2];
int a[MAXN];

int query(int id, int l, int r, int ql, int qr) {
    // تأكد إذا لا يتقاطعان
    if (ql > r || l > qr) {
        return INT_MAX;
    }

    // بالكامل [l, r] يشمل [ql, qr] تأكد إذا
    if (ql <= l && r <= qr) {
        return seg[id];
    }

    // قم بالاستدعاء الذاتي والدمج
    int m = (l + r) / 2;
    return min(query(id * 2, l, m, ql, qr), query(id * 2 + 1, m + 1, r, ql, qr));
}

void pointUpdate(int j, int v) {
    a[j - 1] = v;

    int idx = j + N - 1;
    seg[idx] = v;

    // أعد بناء جميع الآباء
    for (int i = idx / 2; i > 0; i /= 2) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        seg[i + N] = a[i];
    }

    for (int i = n + N; i < 2*N; i++) {
        seg[i] = INT_MAX;  // segment treeالقيم المضافة تعتمد على نوع ال
    }

    for (int i = N - 1; i > 0; i--) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int k, u;
            cin >> k >> u;
            pointUpdate(k, u);
        } else {
            int ql, qr;
            cin >> ql >> qr;

            cout << query(1, 1, N, ql, qr) << "\n";
        }
    }
}

ما هي Segment Tree؟