Segment Trees

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

في هذا القسم يُفترض أن كل شيء مرقم ابتداءً من 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 يمثلون عنصرًا واحدًا فقط، بينما تقوم internal nodes بدمج طفليها بأخذ مجموع قيمتيهما.

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

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

عدد الـnodes

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

الحشو

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

مثال

إذا غيرنا المثال السابق إلى [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 تقابل الموقع i - N + 1 في المصفوفة الأصلية.

الاستعلام

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

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

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

1. إذا كان المجالان [ql, qr] و[l, r] غير متقاطعين تمامًا، يتم تجاهل الـnode الحالي لأنه لا يسهم في الاستعلام.
   
2. إذا كان المجال [ql, qr] يغطي بالكامل المجال [l, r]، نقوم بإرجاع القيمة المخزنة في الـnode الحالي.
   
3. خلاف ذلك، نقسم المجال عند المنتصف 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 إلى القيمة v. لتنفيذ ذلك نقوم بتحديث الـleaf node في الموضع j + N - 1 ثم نعيد حساب جميع قيم الـinternal node.

عدد الآباء لكل leaf node j + N - 1 هو logn. لذلك فإن تعقيد تحديث النقطة هو \(O(\log n)\).

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

عند بناء segment tree لدينا فقط المصفوفة الأصلية a (مرقمة ابتداء من ال0) وحجمها n.

حجم الشجرة

أولًا نحتاج إلى حساب عدد الـleaf nodes N. يمكن حسابه بطريقتين:

إما باستخدام معادلة:

int N = 1 << (32 - __builtin_clz(n - 1));

أو باستخدام حلقة:

int N;
for (N = 1; N < n; N *= 2); // ال; مهمة جدا

حجم الشجرة سيكون 2*N.

int seg[2*N]

بناء segment tree

بناء الـleaf nodes

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

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]; // دمج قيم الطفلين
}

الاستعلامات

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);
}

تحديث الـleaf node

void pointUpdate(int j, int v){
    a[j] = 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

Dynamic Range Minimum Queries

CSES easy

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

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

Solution

سنقوم ببناء segment tree للقيمة الصغرى ونطبق الاستعلامات وتحديثات leaf nodes مباشرة عليها.

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

const int MAXN = 200000;
const int N = (1 << (32 - __builtin_clz(MAXN - 1)));

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; 
    }
    
    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; 
    }

    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";
        }
    }

}