Range query (computer science)
کمپیوٹر سائنس میں، رینج استفسار کا مسئلہ ایک صف کے اندر عناصر کے دیئے گئے وقفے کے حوالے سے کئی سوالات کے موثر جواب دینے پر مشتمل ہوتا ہے۔ مثال کے طور پر، ایک عام کام، جسے رینج کم از کم استفسار کے نام سے جانا جاتا ہے، اعداد کی فہرست کے اندر دی گئی حد کے اندر سب سے چھوٹی قدر تلاش کرنا ہے۔ تعریف ایک فنکشن کو دیکھتے ہوئے جو ایک صف کو قبول کرتا ہے، ایک صف پر ایک رینج استفسار دو اشارے لیتا ہے اور جب ذیلی صف پر لاگو ہوتا ہے تو اس کا نتیجہ واپس کرتا ہے۔ مثال کے طور پر، ایک فنکشن کے لیے جو ایک صف میں تمام اقدار کا مجموعہ واپس کرتا ہے، رینج استفسار رینج میں موجود تمام اقدار کا مجموعہ واپس کرتا ہے۔ حل پریفیکس سم ایرے رینج سم سوالات کا جواب مستقل وقت اور لکیری جگہ میں ان پٹ کے برابر لمبائی کی صف کو پہلے سے کمپیوٹ کرکے دیا جا سکتا ہے تاکہ ہر انڈیکس کے لیے، عنصر ان کے پہلے عناصر کا مجموعہ ہو۔ اس کے بعد کسی بھی استفسار کا حساب مندرجہ ذیل طریقے سے کیا جا سکتا ہے: اس حکمت عملی کو کسی بھی دوسرے بائنری آپریشن تک بڑھایا جا سکتا ہے جس کا الٹا فعل اچھی طرح سے متعین اور آسانی سے قابل حساب ہو۔ اسے اسی طرح کی پری پروسیسنگ کے ساتھ دو جہتی صفوں تک بھی بڑھایا جا سکتا ہے۔ متحرک رینج کے سوالات مسئلہ کا ایک زیادہ مشکل ذیلی سیٹ متحرک ڈیٹا پر رینج کے سوالات کو انجام دینے پر مشتمل ہوتا ہے۔ یعنی وہ ڈیٹا جو ہر استفسار کے درمیان تبدیل ہو سکتا ہے۔ صف کی اقدار کو مؤثر طریقے سے اپ ڈیٹ کرنے کے لیے، سیگمنٹ ٹری جیسے زیادہ نفیس ڈیٹا ڈھانچے ضروری ہیں۔ مثال سیمی گروپ آپریٹرز جب کسی رینج استفسار میں دلچسپی کا فنکشن سیمی گروپ آپریٹر ہوتا ہے، تو تصور کی ہمیشہ وضاحت نہیں کی جاتی ہے، لہذا پچھلے حصے میں حکمت عملی کام نہیں کرتی ہے۔ اینڈریو یاؤ نے دکھایا کہ رینج کے سوالات کا ایک موثر حل موجود ہے جس میں سیمی گروپ آپریٹرز شامل ہیں۔ انہوں نے ثابت کیا کہ کسی بھی مستقل کے لیے، وقت اور جگہ کی پری پروسیسنگ فہرستوں پر رینج کے سوالات کا جواب دینے کی اجازت دیتی ہے جہاں وقت میں سیمی گروپ آپریٹر ہے، جہاں ایکرمین فنکشن کا ایک خاص فنکشنل الٹا ہے۔ کچھ سیمی گروپ آپریٹرز ہیں جو قدرے بہتر حل تسلیم کرتے ہیں۔ مثال کے طور پر کب۔ فرض کریں کہ پھر کے کم از کم عنصر کا انڈیکس واپس کرتا ہے۔ پھر متعلقہ کم از کم رینج استفسار کی نشاندہی کرتا ہے۔ ڈیٹا کے کئی ڈھانچے ہیں جو وقت اور جگہ کی پری پروسیسنگ کا استعمال کرتے ہوئے وقت میں رینج کم از کم استفسار کا جواب دینے کی اجازت دیتے ہیں۔ ایسا ہی ایک حل اس مسئلے اور سب سے کم مشترکہ آباؤ اجداد کے مسئلے کے درمیان مساوات پر مبنی ہے۔ ایک صف کے کارٹیسی درخت کی جڑ ہوتی ہے اور بائیں اور دائیں طرف بالترتیب کارٹیسی درخت اور کارٹیسی درخت کے ذیلی درخت ہوتے ہیں۔ رینج کا کم از کم استفسار اور میں سب سے کم مشترکہ آباؤ اجداد ہے۔ کیونکہ سب سے کم مشترکہ آباؤ اجداد کو وقت اور جگہ کی پری پروسیسنگ کا استعمال کرتے ہوئے مستقل وقت میں حل کیا جا سکتا ہے، رینج کم از کم استفسار بھی ہو سکتا ہے۔ حل جب مماثل ہو۔ کارٹیشین درختوں کی تعمیر لکیری وقت میں کی جا سکتی ہے۔ موڈ کسی صف کا موڈ وہ عنصر ہے جو اس میں سب سے زیادہ ظاہر ہوتا ہے۔ مثال کے طور پر کا موڈ ہے۔ ٹائی کی صورت میں، سب سے زیادہ بار بار آنے والے عناصر میں سے کسی کو بھی موڈ کے طور پر منتخب کیا جا سکتا ہے۔ رینج موڈ استفسار پری پروسیسنگ پر مشتمل ہوتا ہے تاکہ ہم کسی بھی رینج میں موڈ تلاش کر سکیں۔ اس مسئلے کو حل کرنے کے لیے کئی ڈیٹا ڈھانچے وضع کیے گئے ہیں، ہم مندرجہ ذیل جدول میں کچھ نتائج کا خلاصہ پیش کرتے ہیں۔ حال ہی میں جارجینسن اور دیگر۔ خلیوں کو استعمال کرنے والے کسی بھی ڈیٹا ڈھانچے کے سیل پروب ماڈل پر ایک نچلی حد ثابت ہوئی۔ میڈین یہ خاص معاملہ خاص دلچسپی کا حامل ہے کیونکہ میڈین کو تلاش کرنے کے کئی استعمال ہوتے ہیں۔ دوسری طرف، میڈین مسئلہ، سلیکشن کے مسئلے کا ایک خاص معاملہ، میڈینز الگورتھم کے میڈین کا استعمال کرتے ہوئے، O (n) میں حل کرنے کے قابل ہے۔ تاہم رینج میڈین سوالات کے ذریعے اس کی عمومی کاری حالیہ ہے۔ ایک رینج میڈین استفسار جہاں A، i اور j کے معمول کے معنی ہیں، کا میڈین عنصر واپس کرتا ہے۔ مساوی طور پر، رینک کا عنصر واپس کرنا چاہیے۔ رینج میڈین سوالات کو سیمی گروپ آپریٹرز کے لیے یاؤ کے نقطہ نظر سمیت اوپر بیان کردہ پچھلے طریقوں میں سے کسی پر عمل کرکے حل نہیں کیا جا سکتا۔ اس مسئلے کی دو شکلوں کا مطالعہ کیا گیا ہے، آف لائن ورژن، جہاں دلچسپی کے تمام کے سوالات ایک بیچ میں دیے جاتے ہیں، اور ایک ورژن جہاں تمام پری پروسیسنگ سامنے کی جاتی ہے۔ آف لائن ورژن کو وقت اور جگہ کے ساتھ حل کیا جا سکتا ہے۔ فوری منتخب الگورتھم کا درج ذیل سڈوکوڈ ظاہر کرتا ہے کہ مختلف عناصر کی غیر ترتیب شدہ صف میں رینک کے عنصر کو کیسے تلاش کیا جائے، تاکہ ہم جس رینج میڈین کو مقرر کرتے ہیں اسے تلاش کیا جا سکے۔ رینج میڈین (A, i, j, r) {اگر A.length () = = 1 ریٹرن A [1] اگر A.low غیر متعین ہے تو m = میڈین (A) A.low = [e میں A | e <= m] A.high = [e میں A | e> m] کا حساب لگائیں کہ A [i, j] کے عناصر کی تعداد جو A.low سے تعلق رکھتی ہے اگر r <= t تو ریٹرن رینج میڈین (A.low، i, j, r) بصورت دیگر ریٹرن رینج میڈین (A.high، i, j, r-t)} پروسیجر پارٹیشنز، 's میڈین' کا استعمال کرتے ہوئے، دو صفوں میں اور جہاں سابقہ شامل ہے۔ اگر ہم جانتے ہیں کہ اس کے عناصر کی تعداد ختم ہوتی ہے اور یہ تعداد اس سے بڑی ہے تو ہمیں رینک کے عنصر کو تلاش کرتے رہنا چاہیے ؛ بصورت دیگر ہمیں رینک کے عنصر کو تلاش کرنا چاہیے۔ تلاش کرنے کے لیے، زیادہ سے زیادہ انڈیکس تلاش کرنا کافی ہے جیسا کہ اندر ہے اور زیادہ سے زیادہ انڈیکس جیسا کہ اندر ہے۔ پھر۔ پارٹیشننگ حصے پر غور کیے بغیر کسی بھی استفسار کی کل لاگت یہ ہے کہ زیادہ تر ریکرشن کالز کی جاتی ہیں اور ان میں سے ہر ایک میں صرف مستقل تعداد میں آپریشن کیے جاتے ہیں (فریکشنل کیسکیڈنگ کی قیمت حاصل کرنے کے لیے استعمال کیا جانا چاہیے)۔ اگر میڈینز کو تلاش کرنے کے لیے ایک لکیری الگورتھم استعمال کیا جاتا ہے، تو رینج میڈین سوالات کے لیے پری پروسیسنگ کی کل لاگت ہے۔ مسئلہ کے آن لائن ورژن کو حل کرنے کے لیے الگورتھم میں بھی ترمیم کی جا سکتی ہے۔ اکثریتی اشیاء کے دیئے گئے سیٹ میں بار بار عناصر تلاش کرنا ڈیٹا مائننگ میں سب سے اہم کاموں میں سے ایک ہے۔ جب زیادہ تر اشیاء کی تعدد ایک جیسی ہو تو بار بار عناصر تلاش کرنا ایک مشکل کام ہو سکتا ہے۔ لہذا، یہ زیادہ فائدہ مند ہو سکتا ہے اگر ایسی اشیاء کا پتہ لگانے کے لیے اہمیت کی کچھ حد استعمال کی جائے۔ صف کی اکثریت کو تلاش کرنے کے لیے سب سے مشہور الگورتھم میں سے ایک بوئیر اور مور نے تجویز کیا تھا جسے بوئیر-مور اکثریت ووٹ الگورتھم کے نام سے بھی جانا جاتا ہے۔ بوئیر اور مور نے ایک الگورتھم کی تجویز پیش کی تاکہ سٹرنگ کے اکثریتی عنصر (اگر اس کے پاس ہے) کو وقت پر تلاش کیا جا سکے اور جگہ کا استعمال کیا جا سکے۔ بوئیر اور مور کے کام کے تناظر میں اور عام طور پر، آئٹمز کے ایک سیٹ میں اکثریت عنصر (مثال کے طور پر سٹرنگ یا ایک صف) وہ ہے جس کی مثالوں کی تعداد اس سیٹ کے سائز کے نصف سے زیادہ ہو۔ کچھ سال بعد، مشرا اور گریس نے موازنہ کا استعمال کرتے ہوئے بوئر اور مور کے الگورتھم کے ایک زیادہ عمومی ورژن کی تجویز پیش کی تاکہ ایک صف میں موجود تمام آئٹمز کو تلاش کیا جا سکے جن کی متعلقہ تعدد کچھ حد سے زیادہ ہو۔ رینج اکثریت استفسار وہ ہے جو سائز کے ڈیٹا ڈھانچے (مثال کے طور پر ایک صف) کی ذیلی رینج کو دیکھتے ہوئے، تمام الگ الگ آئٹمز کا سیٹ واپس کرتا ہے جو اس دی گئی رینج میں (یا کچھ اشاعتوں میں برابر) اوقات سے زیادہ ظاہر ہوتے ہیں۔ مختلف ڈھانچوں میں جو رینج-اکثریت کے سوالات کی حمایت کرتے ہیں، یا تو جامد (پری پروسیسنگ کے دوران مخصوص) یا متحرک (استفسار کے وقت مخصوص) ہو سکتے ہیں۔ اس طرح کے بہت سے نقطہ نظر اس حقیقت پر مبنی ہیں کہ، رینج کے سائز سے قطع نظر، کسی دیئے گئے کے لیے کم از کم متعلقہ تعدد کے ساتھ زیادہ سے زیادہ الگ امیدوار ہو سکتے ہیں۔ ان امیدواروں میں سے ہر ایک کی مستقل وقت میں تصدیق کرنے سے استفسار کا وقت حاصل ہوتا ہے۔ رینج اکثریت استفسار اس لحاظ سے سڑنے کے قابل ہوتا ہے کہ پارٹیشن کے ساتھ کسی رینج میں-اکثریت اور یا تو میں سے کسی ایک میں-اکثریت ہونی چاہیے۔ اس سڑنے کی وجہ سے، کچھ ڈیٹا ڈھانچے رینج ٹری میں استفسار کی حد کے اختتامی نکات کے سب سے کم مشترکہ آباؤ اجداد (ایل سی اے) کو تلاش کرکے اور امیدواروں کے دو سیٹوں (سائز کے) کی توثیق کرکے ایک جہتی صفوں پر اکثریت کے سوالات کا جواب دیتے ہیں۔ ہر اختتامی نقطہ سے سب سے کم مشترکہ آباؤ اجداد مستقل وقت میں جس کے نتیجے میں استفسار کا وقت ہوتا ہے۔ دو جہتی صف گیگی اور دیگر۔ ایک ڈیٹا ڈھانچہ تجویز کیا جو ایک صف پر رینج اکثریت کے سوالات کی حمایت کرتا ہے۔ اس ڈیٹا ڈھانچے میں ہر استفسار کے لیے ایک حد اور ایک آئتاکار رینج متعین کی گئی ہے، اور ان تمام عناصر کا مجموعہ جن کی متعلقہ تعدد (اس آئتاکار رینج کے اندر) اس سے زیادہ یا اس کے برابر ہے، آؤٹ پٹ کے طور پر واپس کیا جاتا ہے۔ یہ ڈیٹا ڈھانچہ متحرک حد (استفسار کے وقت مخصوص) اور ایک پری پروسیسنگ حد کی حمایت کرتا ہے جس کی بنیاد پر اسے بنایا گیا ہے۔ پری پروسیسنگ کے دوران، صف پر عمودی اور افقی وقفوں کا ایک مجموعہ بنایا جاتا ہے۔ عمودی اور افقی وقفہ مل کر ایک بلاک بناتے ہیں۔ ہر بلاک ایک سپر بلاک کا حصہ ہے جو خود سے نو گنا بڑا ہے (بلاک کے افقی وقفے سے تین گنا بڑا اور اس کے عمودی وقفے سے تین گنا بڑا)۔ ہر بلاک کے لیے امیدواروں کا ایک مجموعہ (زیادہ سے زیادہ عناصر کے ساتھ) ذخیرہ کیا جاتا ہے جو ان عناصر پر مشتمل ہوتا ہے جن کی متعلقہ تعدد کم از کم اس کے متعلقہ سپر بلاک میں ہوتی ہے (جیسا کہ اوپر ذکر کیا گیا ہے)۔ ان عناصر کو ان کی تعدد کے مطابق غیر بڑھتی ہوئی ترتیب میں محفوظ کیا جاتا ہے اور یہ دیکھنا آسان ہے کہ، کوئی بھی عنصر جس کی نسبتا تعدد کم از کم کسی بلاک میں ہو اسے اپنے امیدواروں کا مجموعہ ظاہر کرنا چاہیے۔ ہر اکثریتی استفسار کا جواب پہلے استفسار بلاک، یا وقت پر فراہم کردہ استفسار مستطیل میں موجود سب سے بڑے بلاک کو تلاش کرکے دیا جاتا ہے۔ حاصل کردہ استفسار بلاک کے لیے، پہلے امیدواروں کو وقت پر واپس کر دیا جاتا ہے (تصدیق کیے بغیر)، لہذا یہ عمل کچھ غلط مثبت واپس کر سکتا ہے۔ بہت سے دوسرے ڈیٹا ڈھانچے (جیسا کہ ذیل میں بحث کی گئی ہے) نے ہر امیدوار کی مستقل وقت میں تصدیق کے لیے طریقے تجویز کیے ہیں اور اس طرح استفسار کے وقت کو برقرار رکھتے ہوئے کوئی غلط مثبت نہیں دیتے ہیں۔ جن صورتوں میں استفسار بلاک اس سے چھوٹا ہے انہیں مندرجہ ذیل فارم کے اس ڈیٹا ڈھانچے کی مختلف مثالوں کو محفوظ کرکے سنبھالا جاتا ہے:-th مثال کی پری پروسیسنگ کی حد کہاں ہے۔ اس طرح، استفسار کے لیے-th مثال سے چھوٹے بلاکس سے پوچھ گچھ کی جاتی ہے۔ جیسا کہ اوپر ذکر کیا گیا ہے، اس ڈیٹا ڈھانچے میں استفسار کا وقت ہوتا ہے اور اس کی ہفمین انکوڈ شدہ کاپی کو محفوظ کرکے تھوڑی سی جگہ درکار ہوتی ہے (عنصر کو نوٹ کریں اور ہفمین کوڈنگ بھی دیکھیں)۔ ایک جہتی صفاں چن اور دیگر۔ ایک اعداد و شمار کے ڈھانچے کی تجویز پیش کی گئی جس میں ایک جہتی صف، (استفسار کے وقت مخصوص) اور ایک حد (استفسار کے وقت مخصوص) دی گئی ہے، جو جگہ کے الفاظ کی ضرورت کے وقت میں تمام اکثریت کی فہرست واپس کرنے کے قابل ہے۔ اس طرح کے سوالات کا جواب دینے کے لیے، چن اور دیگر۔ یہ نوٹ کرتے ہوئے شروع کریں کہ ایک ڈیٹا ڈھانچہ موجود ہے جو ٹاپ-کے سب سے زیادہ بار بار آئٹمز کو وقت کی حد میں واپس کرنے کے قابل ہے جس میں جگہ کے الفاظ کی ضرورت ہوتی ہے۔ یک جہتی صف کے لیے، یک طرفہ ٹاپ-کے رینج استفسار کو شکل کا ہونے دیں۔ حدود کی زیادہ سے زیادہ حد کے لیے جس میں کسی الگ عنصر کی تعدد میں کوئی تبدیلی نہیں ہوتی (اور اس کے برابر)، ایک افقی لکیر کا حصہ بنایا جاتا ہے۔ اس لائن سیگمنٹ کا-وقفہ اس سے مطابقت رکھتا ہے اور اس کی-ویلیو اس کے برابر ہے۔ چونکہ بالکل ایک الگ عنصر کی تعدد کو تبدیل کرنے کے لیے ہر عنصر کو شامل کرنا، مذکورہ بالا عمل لائن سیگمنٹ بناتا ہے۔ مزید برآں، عمودی لکیر کے لیے اسے کاٹنے والے تمام افقی لکیر کے حصوں کو ان کی تعدد کے مطابق ترتیب دیا جاتا ہے۔ نوٹ کریں کہ،-وقفہ کے ساتھ ہر افقی لائن کا حصہ بالکل ایک الگ عنصر سے مطابقت رکھتا ہے، جیسے کہ۔ اس کے بعد ایک ٹاپ-کے استفسار کا جواب عمودی کرن کو گولی مار کر اور اسے عبور کرنے والے پہلے افقی لائن کے حصوں کی اطلاع دے کر دیا جا سکتا ہے (اوپر سے یاد رکھیں کہ یہ لائن لائن کے حصے پہلے ہی ان کی تعدد کے مطابق ترتیب دیے گئے ہیں)۔ چن اور دیگر۔ پہلے ایک رینج ٹری بنائیں جس میں ہر برانچنگ نوڈ یک طرفہ رینج ٹاپ-کے سوالات کے لیے اوپر بیان کردہ ڈیٹا ڈھانچے کی ایک کاپی ذخیرہ کرتا ہے اور ہر پتی ایک عنصر کی نمائندگی کرتا ہے۔ ہر نوڈ پر ٹاپ-کے ڈیٹا ڈھانچہ اس نوڈ کے ذیلی درختوں میں موجود اقدار کی بنیاد پر بنایا گیا ہے اور اس کا مقصد یک طرفہ رینج ٹاپ-کے سوالات کا جواب دینا ہے۔ براہ کرم نوٹ کریں کہ ایک جہتی صف کے لیے، ایک رینج ٹری کو دو حصوں میں تقسیم کر کے اور دونوں حصوں پر دہرا کر بنایا جا سکتا ہے ؛ لہذا، نتیجے میں آنے والے رینج ٹری کا ہر نوڈ ایک رینج کی نمائندگی کرتا ہے۔ یہ بھی دیکھا جا سکتا ہے کہ اس رینج ٹری کے لیے جگہ کے الفاظ کی ضرورت ہوتی ہے، کیونکہ اس میں سطحیں ہوتی ہیں اور ہر سطح میں نوڈس ہوتے ہیں۔ مزید برآں، چونکہ رینج ٹری کی ہر سطح پر تمام نوڈس میں ان کے ذیلی درختوں کے کل عناصر ہوتے ہیں اور چونکہ سطحیں ہیں، اس رینج ٹری کی جگہ کی پیچیدگی ہے۔ اس ڈھانچے کا استعمال کرتے ہوئے، ایک رینج اکثریت کے استفسار کا جواب مندرجہ ذیل ہے۔ سب سے پہلے، لیف نوڈس کا سب سے کم مشترکہ آباؤ اجداد (ایل سی اے) اور مستقل وقت میں پایا جاتا ہے۔ نوٹ کریں کہ ایک ڈیٹا ڈھانچہ موجود ہے جس میں جگہ کے ٹکڑوں کی ضرورت ہوتی ہے جو وقت پر ایل سی اے کے سوالات کا جواب دینے کے قابل ہے۔ آئیے اور کے ایل سی اے کی نشاندہی کرتے ہیں، رینج اکثریت کے سوالات (جیسا کہ اوپر اور میں بیان کیا گیا ہے) کی سڑن کو استعمال کرتے ہوئے اور اس کے مطابق، دو طرفہ رینج کے استفسار کو دو یک طرفہ رینج ٹاپ-کے سوالات (سے اور) میں تبدیل کیا جا سکتا ہے۔ یہ دو یک طرفہ رینج ٹاپ-کے سوالات وقت کے ساتھ اپنی متعلقہ حدود میں سب سے زیادہ بار بار آنے والے عناصر کو واپس کرتے ہیں۔ یہ بار بار آنے والے عناصر اکثریت کے لیے امیدواروں کا مجموعہ بناتے ہیں جن میں امیدوار ہوتے ہیں جن میں سے کچھ غلط مثبت ہو سکتے ہیں۔ اس کے بعد ہر امیدوار کا ایک لکیری اسپیس ڈیٹا ڈھانچہ (جیسا کہ لیما 3 انچ میں بیان کیا گیا ہے) کا استعمال کرتے ہوئے مستقل وقت میں جائزہ لیا جاتا ہے جو وقت کے ساتھ اس بات کا تعین کرنے کے قابل ہوتا ہے کہ آیا کسی صف کی دی گئی ذیلی رینج میں کسی خاص عنصر کی کم از کم مثالیں موجود ہیں یا نہیں۔ ٹری پاتھ گیگی اور دیگر۔ ایک ڈیٹا ڈھانچہ تجویز کیا جو اس طرح کے سوالات کی حمایت کرتا ہے کہ، دو نوڈس دیئے گئے ہیں اور ایک درخت میں، ان عناصر کی فہرست کی اطلاع دینے کے قابل ہیں جن کی نسبتا تعدد ایک سے دوسرے کے راستے سے زیادہ ہے۔ مزید رسمی طور پر، ایک لیبل شدہ درخت ہونے دیں جس میں ہر نوڈ کے سائز کے حروف تہجی سے ایک لیبل ہوتا ہے۔ نوڈ کے لیبل کو ظاہر کرتے ہیں۔ آئیے اس منفرد راستے کی نشاندہی کریں جس میں درمیانی نوڈس کو اس ترتیب میں درج کیا گیا ہے جس میں ان کا دورہ کیا گیا ہے۔ دی گئی، اور ایک مقررہ (پری پروسیسنگ کے دوران مخصوص) حد، ایک استفسار کو ان تمام لیبلز کا سیٹ واپس کرنا ہوگا جو بار بار ظاہر ہوتے ہیں۔ اس ڈیٹا ڈھانچے کی تعمیر کے لیے، پہلے نوڈس کو نشان زد کیا جاتا ہے۔ یہ کسی بھی نوڈ کو نشان زد کرکے کیا جا سکتا ہے جس کا فاصلہ کم از کم تینوں (اونچائی) کے نچلے حصے سے ہے اور جس کی گہرائی اس سے تقسیم ہوتی ہے۔ ایسا کرنے کے بعد، یہ مشاہدہ کیا جا سکتا ہے کہ ہر نوڈ اور اس کے قریب ترین نشان زدہ آباؤ اجداد کے درمیان فاصلہ اس سے کم ہے۔ ایک نشان زدہ نوڈ کے لیے، مختلف ترتیبات (جڑ کی طرف راستے) محفوظ کیے جاتے ہیں، جہاں نوڈ کے براہ راست والدین کا لیبل واپس ہوتا ہے۔ دوسرے طریقے سے کہیں، ہر نشان زدہ نوڈ کے لیے، جڑ کی طرف دو لمبائی (پلس نوڈ کے لیے ایک) کی طاقت کے ساتھ تمام راستوں کا سیٹ محفوظ کیا جاتا ہے۔ مزید برآں، ہر ایک کے لیے، تمام اکثریتی امیدواروں کا سیٹ محفوظ کیا جاتا ہے۔ مزید خاص طور پر، ان میں تمام اکثریت یا لیبلز کا مجموعہ ہوتا ہے جو ایک سے زیادہ بار ظاہر ہوتے ہیں۔ یہ دیکھنا آسان ہے کہ امیدواروں کے سیٹ میں ہر ایک کے لیے زیادہ سے زیادہ الگ الگ لیبل ہو سکتے ہیں۔ گیگی اور دیگر۔ پھر نوٹ کریں کہ کسی بھی نشان زدہ نوڈ سے اس کے آباؤ اجداد میں سے کسی ایک تک جانے والے راستے میں تمام اکثریت کا مجموعہ کچھ (لیما 2 انچ) میں شامل ہے کیونکہ لمبائی کے برابر ہے اس طرح ایک موجود ہے جس کی لمبائی x اور z کے درمیان ہے۔ اس طرح کے وجود کا مطلب یہ ہے کہ سے راستے میں اکثریت میں اکثریت ہونی چاہیے، اور اس طرح اس میں ظاہر ہونا چاہیے۔ یہ دیکھنا آسان ہے کہ اس ڈیٹا ڈھانچے کے لیے جگہ کے الفاظ کی ضرورت ہوتی ہے، کیونکہ جیسا کہ تعمیر کے مرحلے میں اوپر ذکر کیا گیا ہے کہ نوڈس کو نشان زد کیا جاتا ہے اور ہر نشان زدہ نوڈ کے لیے کچھ امیدوار سیٹ محفوظ کیے جاتے ہیں۔ تعریف کے مطابق، اس طرح کے سیٹوں کے ہر نشان زدہ نوڈ کے لیے اسٹورز ہوتے ہیں، جن میں سے ہر ایک میں امیدوار ہوتے ہیں۔ لہذا، اس ڈیٹا ڈھانچے کے لیے جگہ کے الفاظ کی ضرورت ہوتی ہے۔ براہ کرم نوٹ کریں کہ ہر نوڈ بھی اسٹور کرتا ہے جو راستے سے جڑ تک کی مثالوں کی تعداد کے برابر ہے، اس سے جگہ کی پیچیدگی میں اضافہ نہیں ہوتا ہے کیونکہ یہ صرف فی نوڈ الفاظ کی مستقل تعداد کا اضافہ کرتا ہے۔ دو نوڈس کے درمیان ہر استفسار کا جواب رینج-اکثریت کے سوالات کی سڑنے کی خاصیت (جیسا کہ اوپر بیان کیا گیا ہے) کا استعمال کرکے اور استفسار کے راستے کو چار ذیلی راستوں میں توڑ کر دیا جا سکتا ہے۔ اور کے ساتھ اور بالترتیب قریب ترین نشان زد آباؤ اجداد ہونے کے ساتھ سب سے کم مشترکہ آباؤ اجداد بنیں۔ جانے کا راستہ بالترتیب آنے اور جانے کے راستوں میں بٹ جاتا ہے (ان راستوں کا سائز تعریف کے لحاظ سے چھوٹا ہوتا ہے، ان سب کو امیدوار سمجھا جاتا ہے)، اور آنے اور جانے کے راستے (جیسا کہ اوپر بیان کیا گیا ہے مناسب تلاش کرکے اور اس کے تمام لیبلز کو امیدواروں کے طور پر غور کرکے)۔ براہ کرم نوٹ کریں کہ باؤنڈری نوڈس کو اسی کے مطابق ہینڈل کرنا پڑتا ہے تاکہ یہ تمام ذیلی راستے جداگانہ ہوں اور ان سب سے امیدواروں کا ایک مجموعہ اخذ کیا جائے۔ اس کے بعد ان امیدواروں میں سے ہر ایک کی تصدیق استفسار کے امتزاج کا استعمال کرتے ہوئے کی جاتی ہے جو نوڈ کے سب سے نچلے آباؤ اجداد کو واپس کرتا ہے جس میں لیبل اور ہر نوڈ کے فیلڈز ہوتے ہیں۔ - بٹ رام اور سائز کے حروف تہجی پر، لکیری جگہ کی ضروریات کے ساتھ وقت پر استفسار کا جواب دیا جا سکتا ہے۔ لہذا، وقت پر ہر امیدوار کی تصدیق کرنے کے نتیجے میں راستے پر موجود تمام اکثریت کے سیٹ کو واپس کرنے کے لیے کل استفسار کا وقت ملتا ہے۔ متعلقہ مسائل اوپر بیان کردہ تمام مسائل کا مطالعہ اعلی جہتوں کے ساتھ ساتھ ان کے متحرک ورژن کے لیے کیا گیا ہے۔ دوسری طرف، رینج کے سوالات کو دیگر ڈیٹا ڈھانچوں جیسے درختوں تک بڑھایا جا سکتا ہے، جیسے کہ سطح کے آباؤ اجداد کا مسئلہ۔ مسائل کا ایک ایسا ہی خاندان آرتھوگنل رینج کے سوالات ہیں، جنہیں گنتی کے سوالات بھی کہا جاتا ہے۔ یہ بھی دیکھیں سطح کے آباؤ اجداد کا مسئلہ سب سے کم عام آباؤ اجداد کے حوالہ جات بیرونی روابط اوپن ڈیٹا اسٹرکچر-باب 13-ڈیٹا اسٹرکچرز فار انٹیجرز ڈیٹا اسٹرکچرز فار رینج میڈین کوئریز-گیرتھ اسٹولٹنگ بروڈل اور ایلن گرونلینڈ جارجینسن ارے