سوال ۲

در داده ساختار درخت بازه (segment tree) که به وسیله‌ی یک آرایه ذخیره شده است برای ذخیره سازی بازه‌ی متناظر با $[0,n)$ از خانه‌ی $1$ حافظه استفاده می‌کنیم.

  1. حال از این به بعد ازای هر بازه مانند $[f,l)$ که در خانه‌ی $i$ ذخیره شده باشد، بچه‌ی چپ آن که متناظر بازه‌ی $[f,\frac{(f+l)}{2})$ است در خانه‌ی $2i$ و بچه‌ی راست که متناظر بازه‌ی $[\frac{(f+l)}{2},l)$ است در خانه‌ی $2i+1$ ذخیره می‌کنیم. برای بازه‌هایی که $l-f \neq 1$ است. فرض کنید می‌خواهیم کمترین مقدار حقیقی و ثابت $k$ را بیابیم که آرایه به طول $kn$ برای ذخیره سازی درخت بازه کافی باشد. این مقدار را بیابید. مثلا مقدار $k=2.7$ کافی نمی‌باشد زیرا اگر $n=6$ باشد، بازه‌ی $[5,6)$ را در خانه‌ی 15ام نگه ‌می‌داریم. پس لااقل آرایه‌ای 16 تایی می‌خواهیم و داریم$6*2.7 < 16$ :.
  2. همان سوال با این فرض که بچه‌ی سمت چپ را متناظر $[f,\frac{(f+l+1)}{2})$ و بچه‌ی راست را متناظر $[\frac{(f+l+1)}{2},l)$ در نظر بگیریم (منظور از حاصل تقسیم بر دو مقدار کف گرفته شده‌ی آن است مانند حاصل تقسیم اعداد صحیح در برنامه‌نویسی).