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.low க்கு சொந்தமான A [i, j] இன் உறுப்புகளின் எண்ணிக்கையை t ஐக் கணக்கிடுங்கள் r <= t என்றால் வரம்பைத் திருப்பவும்மீடியன் (A.low, i, j, r) இல்லையெனில் வரம்பைத் திருப்பவும்மீடியன் (A.high, i, j, r-t)} செயல்முறை பகிர்வுகள், 's மீடியன்' ஐப் பயன்படுத்தி, இரண்டு வரிசைகளாக மற்றும், முந்தையது கொண்டிருக்கும் இடத்தில் அந்த முடிவடையும் உறுப்புகளின் எண்ணிக்கை மற்றும் இந்த எண் அதை விட பெரியது என்று நமக்குத் தெரிந்தால், நாம் தரவரிசையின் உறுப்பைத் தேட வேண்டும்; இல்லையெனில் தரவரிசையின் உறுப்பை நாம் பார்க்க வேண்டும். கண்டுபிடிக்க, உள்ள அதிகபட்ச குறியீட்டையும், உள்ள அதிகபட்ச குறியீட்டையும் கண்டுபிடிப்பது போதுமானது. பிறகு. பகிர்வு பகுதியைக் கருத்தில் கொள்ளாமல் எந்தவொரு வினவலுக்கும் மொத்த செலவு, பெரும்பாலான மறுநிகழ்வு அழைப்புகள் செய்யப்படுவதால், அவை ஒவ்வொன்றிலும் நிலையான எண்ணிக்கையிலான செயல்பாடுகள் மட்டுமே செய்யப்படுகின்றன (பின்ன அடுக்குகளின் மதிப்பைப் பெற பயன்படுத்தப்பட வேண்டும்). மீடியன்களைக் கண்டறிய ஒரு லீனியர் அல்காரிதம் பயன்படுத்தப்பட்டால், ரேஞ்ச் மீடியன் வினவல்களுக்கான முன் செயலாக்கத்தின் மொத்த செலவு. சிக்கலின் ஆன்லைன் பதிப்பைத் தீர்க்க வழிமுறையையும் மாற்றியமைக்கலாம். கொடுக்கப்பட்ட பொருட்களின் தொகுப்பில் அடிக்கடி கூறுகளைக் கண்டறிவது தரவுச் சுரங்கத்தில் மிக முக்கியமான பணிகளில் ஒன்றாகும். பெரும்பாலான உருப்படிகள் ஒரே மாதிரியான அதிர்வெண்களைக் கொண்டிருக்கும்போது அடிக்கடி வரும் கூறுகளைக் கண்டுபிடிப்பது கடினமான பணியாக இருக்கலாம். எனவே, அத்தகைய பொருட்களைக் கண்டறிய சில முக்கியத்துவ வரம்பைப் பயன்படுத்தினால் அது மிகவும் பயனுள்ளதாக இருக்கும். பெரும்பாலான வரிசைகளைக் கண்டுபிடிப்பதற்கான மிகவும் பிரபலமான வழிமுறைகளில் ஒன்று பாயர் மற்றும் மூர் ஆகியோரால் முன்மொழியப்பட்டது, இது பாயர்-மூர் பெரும்பான்மை வாக்கு வழிமுறை என்றும் அழைக்கப்படுகிறது. பாயர் மற்றும் மூர் ஒரு சரத்தின் பெரும்பான்மை உறுப்பை (அதில் ஒன்று இருந்தால்) சரியான நேரத்தில் கண்டறிந்து இடத்தைப் பயன்படுத்த ஒரு வழிமுறையை முன்மொழிந்தனர். பாயர் மற்றும் மூரின் படைப்புகளின் சூழலில் மற்றும் பொதுவாகப் பேசுகையில், உருப்படிகளின் தொகுப்பில் பெரும்பான்மை உறுப்பு (எடுத்துக்காட்டாக சரம் அல்லது ஒரு வரிசை) என்பது அந்த தொகுப்பின் அளவில் பாதிக்கும் மேலான நிகழ்வுகளின் எண்ணிக்கையாகும். சில ஆண்டுகளுக்குப் பிறகு, மிஸ்ரா மற்றும் கிரிஸ் ஆகியோர் பாயர் மற்றும் மூரின் வழிமுறையின் மிகவும் பொதுவான பதிப்பை முன்மொழிந்தனர், ஒப்பீடுகளைப் பயன்படுத்தி அனைத்து உருப்படிகளையும் ஒரு வரிசையில் கண்டுபிடிக்க, அவற்றின் உறவினர் அதிர்வெண்கள் சில வரம்பை விட அதிகமாக உள்ளன. ஒரு வரம்பு-பெரும்பான்மை வினவல் என்பது, ஒரு தரவு கட்டமைப்பின் (எடுத்துக்காட்டாக ஒரு வரிசை) அளவின் துணை வரம்பைக் கொடுத்தால், கொடுக்கப்பட்ட வரம்பில் (அல்லது சில வெளியீடுகளில் சமமான) முறைக்கு மேல் தோன்றும் அனைத்து தனித்துவமான உருப்படிகளின் தொகுப்பையும் திருப்பித் தருகிறது. வரம்பு-பெரும்பான்மை வினவல்களை ஆதரிக்கும் வெவ்வேறு கட்டமைப்புகளில், நிலையானதாக (முன் செயலாக்கத்தின் போது குறிப்பிடப்பட்டுள்ளது) அல்லது மாறும் (வினவல் நேரத்தில் குறிப்பிடப்பட்டுள்ளது) இருக்கலாம். அத்தகைய அணுகுமுறைகளில் பல, வரம்பின் அளவைப் பொருட்படுத்தாமல், கொடுக்கப்பட்டதற்கு குறைந்தபட்சம் ஒப்பீட்டு அதிர்வெண்களுடன் மிகவும் தனித்துவமான வேட்பாளர்கள் இருக்க முடியும் என்ற உண்மையை அடிப்படையாகக் கொண்டவை. இந்த வேட்பாளர்கள் ஒவ்வொருவரையும் நிலையான நேரத்தில் சரிபார்ப்பதன் மூலம், வினவல் நேரம் அடையப்படுகிறது. ஒரு ரேஞ்ச்-மெஜாரிட்டி வினவல் என்பது பகிர்வுகளுடன் ஒரு வரம்பில் ஒரு-மெஜாரிட்டி மற்றும் அல்லது இரண்டில் ஒரு-மெஜாரிட்டியாக இருக்க வேண்டும் என்ற பொருளில் சிதைக்கக்கூடியது. இந்த சிதைக்கக்கூடிய தன்மை காரணமாக, சில தரவு கட்டமைப்புகள் ஒரு பரிமாண வரிசைகளில் பெரும்பான்மை கேள்விகளுக்கு பதிலளிக்கின்றன, ஒரு ரேஞ்ச் மரத்தில் வினவல் வரம்பின் இறுதிப் புள்ளிகளின் மிகக் குறைந்த பொதுவான மூதாதையரை (எல். சி. ஏ) கண்டறிந்து, ஒவ்வொரு இறுதிப் புள்ளியிலிருந்தும் இரண்டு செட் வேட்பாளர்களை (அளவு) சரிபார்க்கிறது. இரு பரிமாண வரிசைகள் Gagie மற்றும் பலர். ஒரு வரிசையில் வரம்பு-பெரும்பான்மை வினவல்களை ஆதரிக்கும் தரவு கட்டமைப்பை முன்மொழிந்தது. இந்த தரவு கட்டமைப்பில் உள்ள ஒவ்வொரு வினவலுக்கும் ஒரு வரம்பு மற்றும் செவ்வக வரம்பு குறிப்பிடப்பட்டுள்ளது, மேலும் தொடர்புடைய அதிர்வெண்களைக் கொண்ட அனைத்து உறுப்புகளின் தொகுப்பும் (அந்த செவ்வக வரம்பிற்குள்) அதிகமாகவோ அல்லது சமமாகவோ வெளியீடாக திருப்பித் தரப்படுகின்றன. இந்த தரவு அமைப்பு மாறும் வரம்புகளை (வினவல் நேரத்தில் குறிப்பிடப்பட்டுள்ளது) மற்றும் அது கட்டமைக்கப்பட்ட ஒரு முன் செயலாக்க வரம்பை ஆதரிக்கிறது. முன் செயலாக்கத்தின் போது, செங்குத்து மற்றும் கிடைமட்ட இடைவெளிகளின் தொகுப்பு வரிசையில் கட்டப்பட்டுள்ளது. ஒன்றாக, ஒரு செங்குத்து மற்றும் ஒரு கிடைமட்ட இடைவெளி ஒரு தொகுதியை உருவாக்குகிறது. ஒவ்வொரு தொகுதியும் தன்னை விட ஒன்பது மடங்கு பெரிய சூப்பர் பிளாக்கின் ஒரு பகுதியாகும் (தொகுதியின் கிடைமட்ட இடைவெளியின் மூன்று மடங்கு அளவு மற்றும் அதன் செங்குத்து இடைவெளியின் மூன்று மடங்கு அளவு). ஒவ்வொரு தொகுதியிலும் குறைந்தபட்சம் அந்தந்த சூப்பர் பிளாக்கில் தொடர்புடைய அதிர்வெண்களைக் கொண்ட (மேலே குறிப்பிட்டுள்ளபடி முன் செயலாக்க வரம்பு) கூறுகளைக் கொண்ட ஒரு தொகுப்பு கேண்டிடேட் (அதிகபட்ச உறுப்புகளுடன்) சேமிக்கப்படுகிறது. இந்த கூறுகள் அவற்றின் அதிர்வெண்களுக்கு ஏற்ப அதிகரிக்காத வரிசையில் சேமிக்கப்படுகின்றன, மேலும் குறைந்தபட்சம் ஒரு தொகுதியில் ஒப்பீட்டு அதிர்வெண் கொண்ட எந்தவொரு உறுப்பும் அதன் கேண்டிடேட்டுகளின் தொகுப்பைக் காட்ட வேண்டும் என்பதைப் பார்ப்பது எளிது. ஒவ்வொரு பெரும்பான்மை வினவலும் முதலில் வினவல் தொகுதியைக் கண்டுபிடிப்பதன் மூலம் பதிலளிக்கப்படுகிறது, அல்லது கொடுக்கப்பட்ட வினவல் செவ்வகத்தில் உள்ள மிகப்பெரிய தொகுதியை சரியான நேரத்தில் கண்டுபிடிப்பதன் மூலம் பதிலளிக்கப்படுகிறது. பெறப்பட்ட வினவல் தொகுதிக்கு, முதல் வேட்பாளர்கள் சரியான நேரத்தில் (சரிபார்க்கப்படாமல்) திருப்பித் தரப்படுகிறார்கள், எனவே இந்த செயல்முறை சில தவறான நேர்மறைகளைத் தரக்கூடும். பல பிற தரவு கட்டமைப்புகள் (கீழே விவாதிக்கப்பட்டுள்ளபடி) ஒவ்வொரு வேட்பாளரையும் நிலையான நேரத்தில் சரிபார்ப்பதற்கான முறைகளை முன்மொழிந்துள்ளன, இதனால் தவறான நேர்மறைகளை வழங்காமல் வினவல் நேரத்தை பராமரிக்கின்றன. வினவல் தொகுதி சிறியதாக இருக்கும் நிகழ்வுகள் பின்வரும் படிவத்தின் இந்த தரவு கட்டமைப்பின் வெவ்வேறு நிகழ்வுகளை சேமிப்பதன் மூலம் கையாளப்படுகின்றனஃ-th நிகழ்வின் முன் செயலாக்க வரம்பு எங்கே. எனவே,-th நிகழ்வை விட சிறிய வினவல் தொகுதிகளுக்கு விசாரிக்கப்படுகிறது. மேலே குறிப்பிட்டுள்ளபடி, இந்த தரவு அமைப்பு வினவல் நேரத்தைக் கொண்டுள்ளது மற்றும் அதன் ஹஃப்மேன்-குறியிடப்பட்ட நகலை சேமிப்பதன் மூலம் சிறிது இடம் தேவைப்படுகிறது (காரணியைக் கவனியுங்கள், மேலும் ஹஃப்மேன் குறியீட்டையும் பார்க்கவும்). ஒரு பரிமாண வரிசைகள் சான் மற்றும் பலர். ஒரு பரிமாண வரிசை, ஒரு துணை வரிசை (வினவல் நேரத்தில் குறிப்பிடப்பட்டுள்ளது) மற்றும் ஒரு வரம்பு (வினவல் நேரத்தில் குறிப்பிடப்பட்டுள்ளது) கொடுக்கப்பட்ட ஒரு தரவு கட்டமைப்பை முன்மொழிந்தது, இடத்தின் வார்த்தைகள் தேவைப்படும் நேரத்தில் அனைத்து பெரும்பான்மைகளின் பட்டியலையும் திருப்பித் தர முடியும். அத்தகைய கேள்விகளுக்கு பதிலளிக்க, சான் மற்றும் பலர். இடத்தின் வார்த்தைகள் தேவைப்படும் நேரத்தில் ஒரு வரம்பில் மேல்-கே மிகவும் அடிக்கடி உருப்படிகளைத் திருப்பித் தரும் திறன் கொண்ட ஒரு தரவு அமைப்பு உள்ளது என்பதைக் குறிப்பிடுவதன் மூலம் தொடங்கவும். ஒரு பரிமாண வரிசைக்கு, ஒரு பக்க மேல்-கே வரம்பு வினவல் வடிவமாக இருக்கட்டும். ஒரு தனித்துவமான தனிமத்தின் அதிர்வெண் மாறாமல் (மற்றும் அதற்கு சமமாக) இருக்கும் அதிகபட்ச வரம்புகளுக்கு, ஒரு கிடைமட்ட கோடு பிரிவு கட்டமைக்கப்படுகிறது. இந்த வரி பிரிவின்-இடைவெளி இதற்கு ஒத்திருக்கிறது மற்றும் அதற்கு சமமான-மதிப்பு உள்ளது. சரியாக ஒரு தனித்துவமான உறுப்பின் அதிர்வெண்ணை மாற்றுவதற்கு ஒவ்வொரு உறுப்பையும் சேர்ப்பதால், மேற்கூறிய செயல்முறை வரி பிரிவுகளை உருவாக்குகிறது. மேலும், ஒரு செங்குத்து கோட்டிற்கு அதை வெட்டுகின்ற அனைத்து அடிவானக் கோடு பிரிவுகளும் அவற்றின் அதிர்வெண்களுக்கு ஏற்ப வரிசைப்படுத்தப்படுகின்றன. - இடைவெளியுடன் கூடிய ஒவ்வொரு கிடைமட்ட கோடு பிரிவும் சரியாக ஒரு தனித்துவமான உறுப்புடன் ஒத்திருக்கிறது என்பதை நினைவில் கொள்க. ஒரு மேல்-கே வினவலுக்கு ஒரு செங்குத்து கதிரை சுடுவதன் மூலமும், அதை வெட்டுகின்ற முதல் கிடைமட்ட கோடு பிரிவுகளைப் புகாரளிப்பதன் மூலமும் பதிலளிக்க முடியும் (மேலே இருந்து நினைவில் கொள்ளுங்கள், இந்த கோடு கோடு பிரிவுகள் ஏற்கனவே அவற்றின் அதிர்வெண்களுக்கு ஏற்ப வரிசைப்படுத்தப்பட்டுள்ளன). சான் மற்றும் பலர். முதலில் ஒரு ரேஞ்ச் ட்ரீயை உருவாக்குங்கள், அதில் ஒவ்வொரு கிளை முனையும் மேலே விவரிக்கப்பட்ட தரவு கட்டமைப்பின் ஒரு நகலை ஒரு பக்க ரேஞ்ச் டாப்-கே வினவல்களுக்கு சேமித்து வைக்கிறது, மேலும் ஒவ்வொரு இலை ஒரு உறுப்பைக் குறிக்கிறது. ஒவ்வொரு முனையிலும் உள்ள மேல்-கே தரவு அமைப்பு அந்த முனையின் துணை மரங்களில் இருக்கும் மதிப்புகளின் அடிப்படையில் கட்டமைக்கப்பட்டுள்ளது, மேலும் இது ஒரு பக்க வரம்பு மேல்-கே கேள்விகளுக்கு பதிலளிப்பதாகும். ஒரு பரிமாண வரிசைக்கு, இரண்டு பகுதிகளாகப் பிரித்து இரண்டு பகுதிகளிலும் மீண்டும் மீண்டும் செய்வதன் மூலம் ஒரு வரம்பு மரத்தை உருவாக்க முடியும் என்பதை நினைவில் கொள்க; எனவே, இதன் விளைவாக வரும் வரம்பு மரத்தின் ஒவ்வொரு முனையும் ஒரு வரம்பைக் குறிக்கிறது. இந்த ரேஞ்ச் டிரிக்கு இடத்தின் சொற்கள் தேவை என்பதையும் காணலாம், ஏனெனில் நிலைகள் உள்ளன மற்றும் ஒவ்வொரு மட்டத்திற்கும் முனைகள் உள்ளன. மேலும், ஒரு ரேஞ்ச் மரத்தின் ஒவ்வொரு மட்டத்திலும் அனைத்து முனைகளும் அவற்றின் துணை மரங்களின் மொத்த கூறுகளைக் கொண்டிருப்பதால், நிலைகள் இருப்பதால், இந்த ரேஞ்ச் மரத்தின் இடைவெளி சிக்கலானது. இந்த கட்டமைப்பைப் பயன்படுத்தி, ஒரு வரம்பு-பெரும்பான்மை வினவலுக்கு பின்வருமாறு பதிலளிக்கப்படுகிறது. முதலாவதாக, இலை முனைகளின் மிகக் குறைந்த பொதுவான மூதாதையர் (எல். சி. ஏ) நிலையான நேரத்தில் காணப்படுகிறது. எல். சி. ஏ கேள்விகளுக்கு சரியான நேரத்தில் பதிலளிக்கும் திறன் கொண்ட இடத்தின் பிட்கள் தேவைப்படும் தரவு அமைப்பு உள்ளது என்பதை நினைவில் கொள்க. எல். சி. ஏ மற்றும், வரம்பு-பெரும்பான்மை வினவல்களின் (மேலே விவரிக்கப்பட்டுள்ளபடி மற்றும் உள்ளபடி) சிதைக்கக்கூடிய தன்மையைப் பயன்படுத்தி, இரு பக்க வரம்பு வினவல்களை இரண்டு ஒரு பக்க வரம்பு மேல்-கே வினவல்களாக (முதல் மற்றும்) மாற்றலாம். இந்த இரண்டு ஒரு பக்க ரேஞ்ச் டாப்-கே வினவல்களும் அந்தந்த வரம்புகளில் ஒவ்வொன்றிலும் மிகவும் அடிக்கடி வரும் டாப்-() கூறுகளை நேரத்திற்குத் திருப்பித் தருகின்றன. இந்த தொடர்ச்சியான கூறுகள்-பெரும்பான்மைக்கான வேட்பாளர்களின் தொகுப்பை உருவாக்குகின்றன, இதில் வேட்பாளர்கள் உள்ளனர், அவற்றில் சில தவறான நேர்மறைகளாக இருக்கலாம். ஒவ்வொரு வேட்பாளரும் ஒரு நேரியல்-இடைவெளி தரவு கட்டமைப்பைப் பயன்படுத்தி நிலையான நேரத்தில் மதிப்பீடு செய்யப்படுகிறார்கள் (லெம்மா 3 இல் விவரிக்கப்பட்டுள்ளபடி) இது ஒரு வரிசையின் கொடுக்கப்பட்ட துணை வரம்பில் ஒரு குறிப்பிட்ட உறுப்பின் குறைந்தபட்ச நிகழ்வுகளாவது உள்ளதா இல்லையா என்பதை சரியான நேரத்தில் தீர்மானிக்க முடியும். மரப் பாதைகள் Gagie மற்றும் பலர். இரண்டு முனைகள் மற்றும் ஒரு மரத்தில் கொடுக்கப்பட்ட கேள்விகளை ஆதரிக்கும் ஒரு தரவு கட்டமைப்பை முன்மொழிந்தது, பாதையில் உள்ளதை விட அதிக உறவினர் அதிர்வெண் கொண்ட கூறுகளின் பட்டியலைப் புகாரளிக்க முடியும். இன்னும் முறைப்படி, ஒவ்வொரு முனையிலும் அளவு எழுத்துக்களில் இருந்து ஒரு முத்திரை இருக்கும் ஒரு முத்திரை குத்தப்பட்ட மரமாக இருக்கட்டும். முனையின் லேபிளைக் குறிக்கலாம். நடுத்தர முனைகள் அவை பார்வையிடப்பட்ட வரிசையில் பட்டியலிடப்பட்டுள்ள தனித்துவமான பாதையை குறிக்கலாம். கொடுக்கப்பட்ட, மற்றும் ஒரு நிலையான (முன் செயலாக்கத்தின் போது குறிப்பிடப்பட்ட) வரம்பு, ஒரு வினவல் பல முறை தோன்றும் அனைத்து லேபிள்களின் தொகுப்பையும் திருப்பித் தர வேண்டும். இந்த தரவு கட்டமைப்பை உருவாக்க, முதல் முனைகள் குறிக்கப்படுகின்றன. குறைந்தபட்சம் மூன்றின் (உயரம்) அடிப்பகுதியில் இருந்து தூரத்தைக் கொண்ட மற்றும் அதன் ஆழத்தால் வகுக்கக்கூடிய எந்த முனையையும் குறிப்பதன் மூலம் இதைச் செய்யலாம். இதைச் செய்த பிறகு, ஒவ்வொரு முனைக்கும் அதன் அருகிலுள்ள குறிக்கப்பட்ட மூதாதையருக்கும் இடையிலான தூரம் அதை விட குறைவாக இருப்பதைக் காணலாம். குறிக்கப்பட்ட முனையைப் பொறுத்தவரை, வெவ்வேறு வரிசைகள் (மூலத்தை நோக்கிய பாதைகள்) சேமிக்கப்படுகின்றன, இதற்காக முனையின் நேரடி பெற்றோரின் லேபிளைத் தருகிறது. வேறுவிதமாகக் கூறினால், குறிக்கப்பட்ட ஒவ்வொரு முனையிலும், மூலத்தை நோக்கி இரண்டு நீளம் கொண்ட அனைத்து பாதைகளின் தொகுப்பும் (முனைக்கு ஒன்று கூட்டல்) சேமிக்கப்படுகிறது. மேலும், ஒவ்வொருவருக்கும், அனைத்து பெரும்பான்மை வேட்பாளர்களின் தொகுப்பும் சேமிக்கப்படுகிறது. மேலும் குறிப்பாக, அனைத்து-பெரும்பான்மைகளின் தொகுப்பு அல்லது பல முறை தோன்றும் லேபிள்களைக் கொண்டுள்ளது. வேட்பாளர்களின் தொகுப்பு ஒவ்வொன்றிற்கும் மிகவும் தனித்துவமான லேபிள்களைக் கொண்டிருக்க முடியும் என்பதைப் பார்ப்பது எளிது. கேகி மற்றும் பலர். குறிக்கப்பட்ட முனையிலிருந்து அதன் மூதாதையர்களில் ஒருவருக்கு செல்லும் பாதையில் உள்ள அனைத்து-பெரும்பான்மைகளின் தொகுப்பும் சிலவற்றில் (லெம்மா 2 அங்குலம்) சேர்க்கப்பட்டுள்ளது என்பதைக் கவனியுங்கள், ஏனெனில் நீளம் சமமாக இருப்பதால் x மற்றும் z க்கு இடையிலான தூரம் இருக்கும் இடத்திற்கு ஒரு நீளம் உள்ளது. அத்தகையவற்றின் இருப்பு, இருந்து வரும் பாதையில் ஒரு-பெரும்பான்மை ஒரு-பெரும்பான்மையாக இருக்க வேண்டும் என்பதைக் குறிக்கிறது, எனவே அதில் தோன்ற வேண்டும். இந்த தரவு கட்டமைப்பிற்கு இடத்தின் சொற்கள் தேவை என்பதைப் பார்ப்பது எளிது, ஏனென்றால் கட்டுமான கட்ட முனைகளில் மேலே குறிப்பிட்டுள்ளபடி குறிக்கப்பட்டு ஒவ்வொரு குறிக்கப்பட்ட முனையிலும் சில கேண்டிடேட் செட்டுகள் சேமிக்கப்படுகின்றன. வரையறையின்படி, அத்தகைய தொகுப்புகளின் ஒவ்வொரு குறிக்கப்பட்ட முனையிலும் கடைகள் உள்ளன, அவை ஒவ்வொன்றும் வேட்பாளர்களைக் கொண்டுள்ளன. எனவே, இந்த தரவு கட்டமைப்பிற்கு இடத்தின் சொற்கள் தேவைப்படுகின்றன. ஒவ்வொரு முனையும் மூலத்திலிருந்து பாதையில் உள்ள நிகழ்வுகளின் எண்ணிக்கைக்கு சமமாக சேமிக்கிறது என்பதை நினைவில் கொள்க, இது ஒரு முனைக்கு நிலையான எண்ணிக்கையிலான சொற்களை மட்டுமே சேர்ப்பதால் இது இட சிக்கலை அதிகரிக்காது. இரண்டு முனைகளுக்கு இடையிலான ஒவ்வொரு வினவலும் மற்றும் வரம்பு-பெரும்பான்மை வினவல்களின் சிதைக்கக்கூடிய பண்பைப் (மேலே விளக்கப்பட்டுள்ளபடி) பயன்படுத்துவதன் மூலமும், வினவல் பாதையை நான்கு துணைப்பாதைகளாக உடைப்பதன் மூலமும் பதிலளிக்க முடியும். மற்றும் மற்றும் முறையே அருகிலுள்ள குறிக்கப்பட்ட மூதாதையர்களுடன் மற்றும் மிகக் குறைந்த பொதுவான மூதாதையராக இருக்கட்டும். இருந்து வரும் பாதை முறையே இருந்து வரும் மற்றும் செல்லும் பாதைகளாக சிதைக்கப்படுகிறது (இந்த பாதைகளின் அளவு வரையறையின்படி சிறியது, இவை அனைத்தும் கேண்டிடேட்டுகளாகக் கருதப்படுகின்றன), மற்றும் இருந்து வரும் மற்றும் செல்லும் பாதைகள் (மேலே விளக்கப்பட்டபடி பொருத்தமானதைக் கண்டறிந்து அதன் அனைத்து லேபிள்களையும் கேண்டிடேட்டுகளாகக் கருத்தில் கொள்வதன் மூலம்). தயவுசெய்து, எல்லை முனைகள் அதற்கேற்ப கையாளப்பட வேண்டும் என்பதை நினைவில் கொள்க, இதனால் இந்த துணைப்பாதைகள் அனைத்தும் வேறுபடுகின்றன, மேலும் அவை அனைத்திலிருந்தும் ஒரு கேண்டிடேட் தொகுப்பு பெறப்படுகிறது. இந்த கேண்டிடேட்டுகள் ஒவ்வொன்றும் வினவல்களின் கலவையைப் பயன்படுத்தி சரிபார்க்கப்படுகின்றன, இது ஒவ்வொரு முனையின் லேபிள் மற்றும் புலங்களைக் கொண்ட முனையின் மிகக் குறைந்த மூதாதையரைத் தருகிறது. ஒரு-பிட் ரேம் மற்றும் அளவின் எழுத்துக்களில், நேரியல் இடத் தேவைகளைக் கொண்டிருக்கும்போது வினவலுக்கு சரியான நேரத்தில் பதிலளிக்க முடியும். எனவே, ஒவ்வொரு வேட்பாளரையும் சரியான நேரத்தில் சரிபார்ப்பது, பாதையில் உள்ள அனைத்து பெரும்பான்மையினரின் தொகுப்பையும் திரும்பப் பெறுவதற்கான மொத்த வினவல் நேரத்தை விளைவிக்கிறது. தொடர்புடைய சிக்கல்கள் மேலே விவரிக்கப்பட்ட அனைத்து சிக்கல்களும் உயர் பரிமாணங்களுக்கும் அவற்றின் மாறும் பதிப்புகளுக்கும் ஆய்வு செய்யப்பட்டுள்ளன. மறுபுறம், ரேஞ்ச் வினவல்கள் மரங்கள் போன்ற நிலை மூதாதையர் சிக்கல் போன்ற பிற தரவு கட்டமைப்புகளுக்கு நீட்டிக்கப்படலாம். இதே போன்ற சிக்கல்களின் குடும்பம் ஆர்த்தோகனல் வரம்பு வினவல்கள் ஆகும், இது எண்ணும் வினவல்கள் என்றும் அழைக்கப்படுகிறது. மேலும் காண்க நிலை மூதாதையர் சிக்கல் குறைந்த பொதுவான மூதாதையர் குறிப்புகள் வெளிப்புற இணைப்புகள் திறந்த தரவு அமைப்பு-அத்தியாயம் 13-தரவு கட்டமைப்புகள் முழு எண்களுக்கான தரவு கட்டமைப்புகள் வரம்பு சராசரி கேள்விகளுக்கான தரவு கட்டமைப்புகள்-கெர்த் ஸ்டோல்டிங் ப்ரோடல் மற்றும் ஆலன் க்ரோன்லண்ட் ஜோர்ஜென்சன் வரிசைகள்