ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของการสืบค้นขนาด N และ Q ซึ่งสามารถมีได้สองประเภท งานของเราคือสร้างโปรแกรมเพื่อแก้ไขแบบสอบถามเพื่ออัปเดตดัชนีที่กำหนดและค้นหา GCD ในช่วง
แบบสอบถามคือ −
ประเภทที่ 1 − {1, index, value} - เพิ่มองค์ประกอบที่ดัชนีที่กำหนดตามค่า
ประเภทที่ 2 − {2, L, R} - ค้นหา GCD ขององค์ประกอบในช่วงดัชนี [L, R]
คำอธิบายปัญหา − เราจำเป็นต้องค้นหา GCD ขององค์ประกอบที่อยู่ในช่วง [L, R] แล้วคืนค่ากลับมา
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] ={5, 1, 7, 3, 8}, Q =3คำถาม:{{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}} ผลลัพธ์
คำอธิบาย
แนวทางการแก้ปัญหา
แนวทางในการแก้ปัญหาคือการใช้ Segment Tree ซึ่งใช้ในการประมวลผล GCD ล่วงหน้าสำหรับอาร์เรย์ ซึ่งจะช่วยลดเวลาในการคำนวณ GCD สำหรับการสืบค้นแต่ละครั้ง
การสร้างและทำงานกับแผนผังกลุ่ม
ต้นไม้เซกเมนต์ที่เราใช้ที่นี่เป็นทรีที่เก็บองค์ประกอบของอาร์เรย์เป็นโหนดปลายสุด และ GCD ขององค์ประกอบเป็นโหนดภายใน
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include ใช้เนมสเปซ std;int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) { if (L <=segL &&R>=segR ) ส่งคืน st[currNode]; ถ้า (segR R) คืนค่า 0; int กลาง =(segL + (segR - segL)/2); int GcdL =calcGcdRangeRec(st, segL, กลาง, L, R, 2 * currNode + 1; int GcdR =calcGcdRangeRec(st, กลาง + 1, segR, L, R, 2 * currNode + 2); ส่งคืน __gcd (GcdL, GcdR);} เป็นโมฆะ updateArrayValueRec (int * st, int L, int R, ดัชนี int, int diff, int currNode) { ถ้า (ดัชนี R) ส่งคืน; st[currNode] =st[currNode] + ความแตกต่าง; ถ้า (R !=L) { int mid =(L + (R - L) / 2); updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1); updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2); }} เป็นโมฆะ updateArrayValue (int arr[], int* st, int n, int index, int newVal) { if (index <0 || index> n - 1) cout <<"Invalid Input"; อื่น { int diff =newVal - arr [ดัชนี]; arr[index] =newVal; updateArrayValueRec(st, 0, n - 1, ดัชนี, ส่วนต่าง, 0); }}int calcGcdRange(int* st, int n, int L, int R) { if (L <0 || R> n - 1 || L> R) { cout <<"Invalid Input"; กลับ -1; } คืนค่า calcGcdRangeRec(st, 0, n - 1, L, R, 0);}int constructGcdST(int arr[], int L, int R, int* st, int currNode) { if (L ==R) { st[currNode] =arr[L]; ผลตอบแทนarr[L]; } int mid =(L + (R - L)/2); int GcdL =constructGcdST(arr, L, mid, st, currNode * 2 + 1); int GcdR =constructGcdST(arr, กลาง + 1, R, st, currNode * 2 + 2); st[currNode] =__gcd(GcdL, GcdR); ส่งคืน st[currNode];}int main () { int arr[] ={ 1, 3, 6, 9, 9, 11 }; int n =sizeof(arr) / sizeof(arr[0]); int Q =3; ข้อความค้นหา int[3][3] ={{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}}; ค่า int =(int)(ceil(log2(n))); ขนาด int =2 * (int)pow (2, ค่า) - 1; int* st =ใหม่ int[ขนาด]; constructGcdST(arr, 0, n - 1, st, 0); for(int i =0; i อินพุต
แบบสอบถาม 1:GCD คือ 3Query 2:กำลังอัปเดตค่า! แบบสอบถาม 3:GCD คือ 1
