لماذا مجموعة الاستعلام عن شجرة الجزء المقابل في معظم $\lceil \log_2{N} ceil$ العقد?

Question

إذا كان صفيف $A[1 \ldots ن]$ ويمثل استخدام شريحة شجرة وجود مجموعات في كل فترة, لماذا مجموعة الاستعلام $[L\ldots ص]$ يعود في معظم $\lceil \log_2{N} ceil$ مجموعات (أو منفصلة فترات)?

إذا جاء عبر هذا البيان أثناء القراءة هذا الجواب.

اقتباس:

تجد منفصلة تغطية الاستعلام مجموعة باستخدام معيار الجزء شجرة الاستعلام الإجراء.نحصل على $O(\log n)$ منفصلة العقد ، اتحاد الذي multisets هو بالضبط مولتيست القيم في استعلام مجموعة.دعونا ندعو تلك multisets $s_1, \النقاط ، s_m$ (مع $m \لو \lceil \log_2 n ceil$).

حاولت البحث عن دليل, ولكن لا يمكن العثور عليه في أي موقع.يمكن لأي شخص أن يساعدني إثبات ذلك ؟

Answer 1

هنا هي الفكرة الأساسية.

السماح ثنائي الفاصل يكون الفاصل الزمني من شكل $$ [2^ب ، 2^ب(أ+1)-1] $$ عدد صحيح لبعض $a,b \geq 0$.

المطالبة 1. إذا $m < 2^n$ ثم أي فاصل من شكل $[0,m-1]$ يمكن أن تكون مكتوبة كما منفصلتين الاتحاد على الأكثر $n$ ثنائي فترات.

برهان. توسيع $م$ كما مبلغا من تقليل صلاحيات 2:$$ m = 2^{a_1} + \cdots + 2^{a_k}.$$ ثم يمكن أن نكتب $$ [0,m-1] = [0,2^{a_1}-1] \كأس [2^{a_1},2^{a_1}+2^{a_2}-1] \كأس \cdots \كأس [2^{a_1} + \cdots + 2^{a_{k-1}},2^{a_1} + \cdots + 2^{a_k}-1].$$

المطالبة 2. إذا $0 \leq m_1 \leq m_2 \leq 2^n$ ثم أي فاصل من شكل $[m_1 ، m_2-1]$ يمكن أن تكون مكتوبة كما منفصلتين الاتحاد على الأكثر $2n$ ثنائي فترات.

برهان. ثنائي التوسع $m_1$ و $m_2$ هو من شكل $m_1 = x0y, m_2 = x1z$, حيث $|y|=|z|$.السماح $m = x 10^{|z|}$.باستخدام المطالبة 1 ، يمكننا التعبير عن $[0,m_2-m-1]$ مثل الاتحاد في معظم $n$ ثنائي فترات.التحول هذه من قبل $م$, نعبر عن $[م ، m_2-1]$ مثل الاتحاد في معظم $n$ ثنائي فترات.وبالمثل ، باستخدام المطالبة 1 يمكننا أن نعبر عن $[0,m-m_1-1]$ مثل الاتحاد في معظم $n$ ثنائي فترات.تحويل وعكس نعبر عن $[m_1,m-1]$ مثل الاتحاد في معظم $n$ ثنائي فترات.

(في كل الحالات يحتاج المرء أن تحقق هذا التحول ، وربما عكس والحافظات فاصل يجري الديناميكية.)