# 範圍LCM查詢

## 例

```arr[] = {2, 4, 6, 9, 10, 8, 7, 5, 14, 1};
Query: {(2, 5), (3, 7), (5, 8)}```
`360 2520 280`

## 算法

1. 聲明兩個 數組.
2. 建立一個 段樹 通過遞歸調用左側孩子和右側孩子的函數。
3. 獲取左子節點和右子節點的LCM。
4. 要獲取數字的LCM，請用左孩子和右孩子的乘積除以他們的GCD。
5. 對於左右兩個查詢，檢查範圍是否無效，然後返回1，否則檢查左邊是否小於節點的起始值，右邊是否大於結束節點的值，然後返回樹的當前值節點。
6. 如果以上任一條件都不成立，則遞歸調用該函數以獲取左節點lcm和右節點lcm，然後調用lcm函數以獲取這些數字的LCM。

### 解釋

House Robber II Leetcode解決方案

## 推薦碼

### 範圍LCM查詢的C ++代碼

```#include<iostream>

using namespace std;

#define MAX 1000

int tree[4*MAX];

int arr[MAX];

int GCD(int a, int b)
{
if (a == 0)
return b;
return GCD(b%a, a);
}
int getLCM(int a, int b)
{
return a*b/GCD(a,b);
}
int solveQuery(int node, int start, int end, int left, int right)
{
if (end < left || start > right)
return 1;

if (left<=start && right >=end)
return tree[node];

int mid = (start+end)/2;
int leftChildgetLCM = solveQuery(2*node, start, mid, left, right);
int rightChildgetLCM = solveQuery(2*node+1, mid+1, end, left, right);
return getLCM(leftChildgetLCM, rightChildgetLCM);
}
void buildTree(int node, int start, int end)
{
if (start==end)
{
tree[node] = arr[start];
return;
}

int mid = (start+end)/2;
buildTree(2*node, start, mid);
buildTree(2*node+1, mid+1, end);

int leftChildgetLCM = tree[2*node];
int rightChildgetLCM = tree[2*node+1];

tree[node] = getLCM(leftChildgetLCM, rightChildgetLCM);
}

int main()
{
arr[0] = 2;
arr[1] = 4;
arr[2] = 6;
arr[3] = 9;
arr[4] = 10;
arr[5] = 8;
arr[6] = 7;
arr[7] = 5;
arr[8] = 14;
arr[9] = 1;
buildTree(1, 0, 9);
cout << solveQuery(1, 0, 9, 2, 5) << endl;

cout << solveQuery(1, 0, 9, 3, 7) << endl;

cout << solveQuery(1, 0, 9, 5, 8) << endl;

return 0;
}
```
```360
2520
280```

### 範圍LCM查詢的Java代碼

```class LCMQueries
{

private static final int MAX = 1000;

private static int tree[] = new int[4 * MAX];

private static int arr[] = new int[MAX];

static int GCD(int a, int b)
{
if (a == 0)
{
return b;
}
return GCD(b % a, a);
}
static int getLCM(int a, int b)
{
return a * b / GCD(a, b);
}
static void buildTree(int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
return;
}

int mid = (start + end) / 2;
buildTree(2 * node, start, mid);
buildTree(2 * node + 1, mid + 1, end);
int leftChildLCM = tree[2 * node];
int rightChildLCM = tree[2 * node + 1];

tree[node] = getLCM(leftChildLCM, rightChildLCM);
}
static int solveQuery(int node, int start,
int end, int left, int right)
{
if (end < left || start > right)
{
return 1;
}

if (left <= start && right >= end)
{
return tree[node];
}

int mid = (start + end) / 2;
int leftChildLCM = solveQuery(2 * node, start, mid, left, right);
int rightChildLCM = solveQuery(2 * node + 1, mid + 1, end, left, right);
return getLCM(leftChildLCM, rightChildLCM);
}
public static void main(String[] args)
{
arr[0] = 2;
arr[1] = 4;
arr[2] = 6;
arr[3] = 9;
arr[4] = 10;
arr[5] = 8;
arr[6] = 7;
arr[7] = 5;
arr[8] = 14;
arr[9] = 1;

buildTree(1, 0, 9);

System.out.println(solveQuery(1, 0, 9, 2, 5));

System.out.println(solveQuery(1, 0, 9, 3, 7));

System.out.println(solveQuery(1, 0, 9, 5, 8));

}
}
```
```360
2520
280```

## 複雜度分析

### 時間複雜度

O（Log N * Log n） 哪裡 “ N” 是數組中元素的數量。 另一個 登錄n 表示查找LCM所需的時間。 此時間複雜度適用於每個查詢。 總時間複雜度為 O（N + Q * Log N * log n）， 這是因為構建樹然後回答查詢需要O（N）時間。

### 空間複雜度

上） 哪裡 “ N” 是數組中元素的數量。 該空間是存儲段樹所必需的。