ابحث عن القيمة القصوى الأصغر من V في صفيف يتكون من وظائف خطية K

Question

آسف لعدم الوضوح في وصف السؤال.

لدي مجموعة مكونة من الطول $ن$ تتكون من $ك$ المصفوفات الفرعية الخطية.نحن نعرّف المصفوفة الفرعية الخطية بأنها مصفوفة فرعية متجاورة من المصفوفة $[ل،ص]$ أين $A[i]-A[i-1] = C$, ، ثابت للجميع $ل<i<=r$.(ملحوظة: $ج$ قد تكون مختلفة بالنسبة للمصفوفات الفرعية المختلفة؛عناصر المصفوفة هي أعداد صحيحة.) يرجى ملاحظة أن المصفوفات الفرعية الخطية ليست منفصلة (يوجد تقاطع عنصر واحد بين أي زوج من المصفوفات الفرعية الخطية المجاورة).على سبيل المثال، يحتوي [1,3,5,4,3,2] على صفيفتين فرعيتين خطيتين:[1،3،5] و [5،4،3،2].[1،3،5،1،2،3] سيكون لها ثلاثة:[1،3،5]، [5،1]، [1،2،3].

أرغب في العثور على استعلامات متعددة للقيمة القصوى التي تكون أقل من القيمة التي تم الاستعلام عنها $V$, ، في $ س (ك) $ و $س(ن)$ الوقت لكل استعلام، مع $س(ك^2)$ و $س(ن)$ المعالجة المسبقة.(افترض أن المصفوفة قد تم تخزينها بالفعل فيما يتعلق بـ ك المصفوفات الفرعية الخطية، ربما من حيث الثابت ج وطول كل مصفوفة فرعية، مع ترتيب المصفوفات الفرعية.لذلك، يتم منحك مصفوفة تحتوي على نقطتي البداية والنهاية لجميع المصفوفات الفرعية الخطية، بالإضافة إلى الثابت الخطي ج, ، كما هو موضح من قبل.لذلك، لا يحتاج المرء إلى اشتقاق المصفوفات الفرعية الخطية في المقام الأول.) بخلاف ذلك، سيكون موضع تقدير وجود دليل (رسمي أم لا) على أنه من غير الممكن القيام بذلك.

وبطبيعة الحال، فإن شجرة البحث الثنائية المتوازنة (BBST) أو مجرد الفرز تحقق الغرض، ولكنها تتطلب ذلك $O(NlogN)$ المعالجة المسبقة، وهو أكثر من اللازم.يستغرق التحقق من أكبر قيمة صالحة داخل كل مصفوفة فرعية $O(ك)$ لكل استعلام، وهو مرة أخرى أكثر من اللازم.فهل من الممكن أن يجمع شيء ما بين هذين الأمرين، ربما؟

لا بأس بالخوارزميات العشوائية طالما أنها تحقق دائمًا الإجابة الصحيحة وتعمل بسرعة كافية في الحالة المتوسطة، على الرغم من تفضيل الخوارزميات الحتمية.

شكرا على اي وجميع الردود.كنت أتساءل عما إذا كان هناك أي بحث في هذا السؤال، ربما؟لا يبدو هذا الموضوع غامضًا جدًا، لكن للأسف لم يكن بحثي كافيًا بما فيه الكفاية.

يحرر:طريقة تبدو مفيدة.

هنا كان خط تفكيري بعد أن طرحت السؤال؛وأتساءل عما إذا كان هذا من شأنه أن يساعد بطريقة أو بأخرى.ويستخدم فكرة modulo كذلك.التهيئة V=0, ، والسماح بتخزين كل صفيف فرعي خطي كـ L,R;أين L هي القيمة الدنيا للصفيف الفرعي و R هي القيمة القصوى.عندما يعطى لنا استعلام عن V, ، نحن بطريقة ما نستبعد العناصر حيث L>V و R<V (ربما باستخدام أبعاد متعددة؟) تقوم بنية البيانات التكميلية بتخزين الحد الأدنى من الاختلاف النظري للعنصر في المصفوفة، وهو ما يشبه L - V mod c[i].لذا، نحتاج الآن بشكل أساسي إلى أن نكون قادرين على تشغيل نطاق يضاف إلى بنية البيانات هذه، ولكن إذا أصبحت قيمة أي عنصر <0 أو >=c[i] يجب إعادة تعيينه (على سبيل المثال.إذا أصبح العنصر يساوي -1 مع c[i]=5 فسيتم إعادة تعيينه إلى 4؛إذا أصبح العنصر يساوي 6 مع نفس c[i] فسيتم إعادة تعيينه إلى 1)؛وأيضًا تشغيل الحد الأدنى من الاستعلامات.

إذا كان من الممكن إنشاء بنية البيانات هذه، فسيتم حل المشكلة.تكمن المشكلة في المودولو، حيث يمكن بسهولة إضافة النطاق واستعلام الحد الأدنى للنطاق باستخدام شجرة المقاطع والانتشار البطيء؛وكذلك استبعاد بعض العناصر.

Answer 1

ليس من الممكن ضمان العثور على القيمة القصوى التي تكون أقل من القيمة التي تم الاستعلام عنها $V$ في $ س (ك) $ الوقت مع المعالجة المسبقة في $س(ن)$ وقت.

ويمكن ملاحظة ذلك بسهولة في الحالة القصوى التالية.يترك $أ$ يكون أي مجموعة من $ن$ الأعداد الصحيحة، والتي تتكون مما يلي $K=N-1$ المصفوفات الفرعية الخطية.

• المصفوفة الفرعية $أ[0]، أ[1]$ مع $C=A[1]-A[0]$.
• المصفوفة الفرعية $أ[1]، أ[2]$ مع $C=A[2]-A[1]$.
• $\كدوتس$
• المصفوفة الفرعية $A[N-2]، A[N-1]$ مع $C=A[N-1]-A[N-2]$.

مع $س(ن)$ المعالجة المسبقة للوقت و $س(ك)=س(ن)$ معالجة الوقت، لن تتمكن الخوارزمية حتى من قراءة بعض الأرقام $أ$ متى $ن$ كبيرة بما فيه الكفاية.(في الواقع، معظم الأرقام في $أ$.) لذا، بالنسبة لبعض القيمة المتساءل عنها $س$, ، ستفشل الخوارزمية في التعرف على ذلك $ف+1$ يظهر في $أ$.

(يمكن جعل الشرح أعلاه أكثر صرامة، على سبيل المثال، باستخدام الطريقة الرسمية للخصم ونموذج حسابي محدد جيدًا).

---

يبدو أن السؤال الأكثر إثارة للاهتمام الذي يجب طرحه هو ما إذا كانت هناك خوارزمية بها $o(N\log N)$ المعالجة المسبقة و $ س (ك) $ لكل استعلام.أو ما إذا كانت هناك خوارزمية مع $س(ن)$ المعالجة المسبقة و $ س (ك) $ لكل استعلام معين $K=o(N)$.هذا يبدو وكأنه سؤال آخر، على أي حال.