# 范围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。

## 代码

### 范围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” 是数组中元素的数量。 该空间是存储段树所必需的。