تحليل الجذر التربيعي

تحليل الجذر التربيعي هي تقنية تسمح بحساب استعلامات على مستوى نطاق بزمن \(O(\sqrt n)\)، مما يحسن الأداء مقارنةً بزمن \(O(n)\) في المصفوفة العادية.

Noteملحوظة

استعلام على مستوى نطاق هو استعلام يطلب حساب قيمة (مثلًا: المجموع، أو القيمة الصغرى، أو القيمة العظمى) لنطاق من العناصر.

هيكل البيانات

لنعتبر مصفوفة \(a\) بطول \(n\). لبناء هيكل تحليل الجذر التربيعي، نقوم أولًا بتقسيم \(a\) إلى كتل بحجم \(\lceil \sqrt{n} \rceil\) (ولنسمِّ هذا الحجم \(sz\)). ثم، لكل كتلة، نحسب القيمة المطلوبة ونخزنها في مصفوفة \(b\)، حيث يمثّل \(b_i\) القيمة المحسوبة للكتلة رقم \(i\).

Noteملحوظة

\(\lceil \sqrt{n} \rceil\) هو \(\sqrt n\) بعد التقريب للأعلى إلى أقرب عدد صحيح.

بما أن \(sz\) يساوي تقريبًا \(\sqrt n\)، فإن عدد الكتل سيكون تقريبًا \(\frac{n}{\sqrt n}\) والذي يساوي \(\sqrt n\).

\(\underbrace{a_0, a_1, \dots, a_{sz-1}}_{b_{0}}, \underbrace{a_{sz}, a_{sz + 1}, \dots, a_{2 * sz - 1}}_{b_{1}}, \dots, \underbrace{a_{(sz - 1) * sz}, a_{(sz - 1) * sz + 1}, \dots, a_{n - 1}}_{b_{sz}}\)

حساب الاستعلامات

افترض أننا نريد معالجة استعلام نطاق من \(l\) إلى \(r\).

الطريقة البسيطة هي المرور على جميع العناصر من \(l\) إلى \(r\) وحساب القيمة المطلوبة. يستغرق ذلك زمنًا قدره \(O(n)\) في أسوأ الحالات.

باستخدام هيكل تحليل الجذر التربيعي، نلاحظ أن النطاق \([l, r]\) يغطي عادةً عدة كتل بشكل كامل، باستثناء الكتلة الأولى (التي تحتوي على \(l\)) والكتلة الأخيرة (التي تحتوي على \(r\)).

للإجابة على الاستعلام بكفاءة، نقوم أولًا بحل الكتلتين المغطاتين جزئيًا كلٌّ على حدة. ثم نمرّ على الكتل المغطاة بالكامل بينهما ونستخدم القيم \(b_i\) المحسوبة مسبقًا. هذا يقلل زمن الاستعلام إلى \(O(\sqrt{n})\).

تحديث نقطة

تطلب بعض المسائل تحديث موقع معيّن \(j\) إلى قيمة جديدة \(v\). نقوم بتحديث \(a[j]\) إلى \(v\) بزمن \(O(1)\). ثم نعيد حساب قيمة الكتلة التي ينتمي إليها \(j\) بزمن \(O(\sqrt{n})\). إذًا التعقيد الكلي للتحديث هو \(O(\sqrt{n})\).

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

لنفترض أننا نريد أن نجيب على استعلامات تطلب حساب القيمة العظمى في نطاق. ### الحسابات المسبقة هنا نقوم ببناء الهيكل<

for (int i = 0; i < n; i++) {
    b[i / sz] = max(a[i], b[i / sz]); // i/sz ينتمي إلى i عنصر
}

الإجابة عن استعلامات

int queryMax(int l, int r) {
    int blockL = l / sz;
    int blockR = r / sz;

    int ans = INT_MIN;

    // حالة خاصة عندما يبدأ النطاق وينتهي في الكتلة نفسها
    if (blockL == blockR) { 
        for(int i = l; i <= r; i++) {
            ans = max(ans, a[i]);
        }
        return ans;
    }

    // حساب الكتلة الأولى
    for (int i = l; i < (blockL + 1) * sz; i++) {
        ans = max(ans, a[i]);
    }

    // حساب الكتل البينية
    for (int i = blockL + 1; i < blockR ; i++) {
        ans = max(ans, b[i]);
    }

    // حساب الكتلة الأخيرة
    for (int i = blockR * sz; i <= r ; i++){
        ans = max(ans , a[i]);
    }

    return ans;
}

تحديث عنصر

void pointUpdate(int j , int v){
    int blockJ = j / sz;

    a[j] = v;
    
    // b[blockJ] إعادة حساب
    b[blockJ] = INT_MIN;

    for (int i = blockJ * sz; i < (blockJ + 1) * sz; i++) {
        b[blockJ] = max(b[blockJ], a[i]);
    }
}

Dynamic Range Minimum Queries

Dynamic Range Minimum Queries

CSES easy

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

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

Solution

هذه المسألة مشابهة للرنامج السابق، ولكن الآن يُطلب منا حساب القيمة الصغرى. هناك بعض الملاحظات البسيطة التي يجب أخذها بعين الاعتبار:

1. المصفوفات معرّفة في النطاق العام ، ولهذا نستخدم MAXN كأكبر قيمة ممكنة لـ \(n\).

2. في الاستعلامات، نقوم بكتابة k-- و l-- و r-- لأن المدخلات مرقمة ابتداء من 1، بينما تنفيذنا يستخدم مصفوفات تبدأ من 0.

#include <iostream>
#include <cmath>    
#include <climits>  

using namespace std;
const int MAXN = 200000;
const int sz = (int)ceil(sqrt(MAXN));
int a[MAXN];
int b[sz]; 

int queryMin(int l, int r) {
    int blockL = l / sz;
    int blockR = r / sz;

    int ans = INT_MAX;

    if (blockL == blockR) { 
        for(int i = l; i <= r; i++) {
            ans = min(ans, a[i]);
        }
        return ans;
    }

    for (int i = l; i < (blockL + 1) * sz; i++) {
        ans = min(ans, a[i]);
    }

    for (int i = blockL + 1; i < blockR ; i++) {
        ans = min(ans, b[i]);
    }

    for (int i = blockR * sz; i <= r ; i++){
        ans = min(ans , a[i]);
    }

    return ans;
}

void pointUpdate(int j , int v){
    int blockJ = j / sz;

    a[j] = v;
    
    b[blockJ] = INT_MAX;

    for (int i = blockJ * sz; i < (blockJ + 1) * sz; i++) {
        b[blockJ] = min(b[blockJ], a[i]);
    }
}

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

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

    for (int i = 0 ; i < sz; i++) {
        b[i] = INT_MAX;
    }

    for (int i = 0; i < n; i++) {
        b[i / sz] = min(a[i], b[i / sz]);
    }

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

        if (type == 1){
            int k , u;
            cin >> k >> u;
            k--;
            pointUpdate(k, u);
        }
        else{
            int l , r;
            cin >> l >> r;
            l--; r--;
            cout << queryMin(l , r) << "\n";
        }
    }
}