# Bài 1: Truy vấn tổng mảng tĩnh
## <span style="color:red;">Cày trâu</span>

- Với mỗi truy vấn $q$ ta sẽ thực hiện tính tổng các phần tử $x$ trong mảng từ vị trí $a$ đến $b$ như yêu cầu của đề. Độ phức tạp là $O(n \times q)$

## <span style="color:red;">Thuật AC</span>

- Ta sẽ sử dụng kĩ thuật dùng mảng để tính tổng cộng dồn. Ta sẽ tạo một mảng $prefix[i]$ để lưu tổng giá trị của các phần tử từ $1$ đến vị trí thứ $i$ -> tổng giá trị từ vị trí thứ $a$ đến vị trí thứ $b$ sẽ là $prefix[b]-prefix[a-1]$. Độ phức tạp là $O(q)$
- VD:

8 4
3 2 4 5 1 1 5 3

Ta sẽ tạo được mảng cộng dồn $prefix[i]$ là:

prefix[1]=x1;
prefix[2]=prefix[1]+x2;
...
prefix[n]=prefix[n-1]+xn;

### Code:

#include<bits/stdc++.h>
using namespace std;
int prefix[200005];
int main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);cin.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        prefix[i]=prefix[i-1]+x;
    }
    for(int i=1;i<=q;i++)
    {
        int a,b;
        cin>>a>>b;
        cout<<prefix[b]-prefix[a-1]<<'\n';    
    }
}

# Bài 2: Mua Quà
## <span style="color:red;">Cày Trâu</span>
- Ta sẽ thử $m$ cách chọn $n$ món quà (thử hết tất cả trường hợp). Độ phức tạp là $O(C^{m}_{n})$
## <span style="color:red;">Thuật AC</span>
- Ta sẽ dùng phương pháp tham lam:
- Nhận xét: Sau khi ta sắp xếp các phần tử theo thứ tự tăng dần và bắt đầu xét từ phần tử có vị trí thứ $m$. Nếu ta lấy phần tử thứ $i$ $(m \leq i \leq n)$ là món quà có giá trị lớn nhất trong $m$ món quà mình chọn thì độ chênh lệch nhỏ nhất chính là phần tử thứ $i$ đang xét trừ cho phần tử thứ $i-m+1$. Độ phức tạp sẽ là $O(n-m+1)$

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);//sắp xếp tăng dần các phần tử mảng a
    long long res=1e18;
    for(int i=m;i<=n;i++)
    {
        long long phu=a[i]-a[i-m+1];//giá trị chênh lệch nhỏ nhất khi a[i] là món quà có giá trị lớn nhất mình chọn
        res=min(res,phu);//lấy giá trị chênh lệch nhỏ nhất
    }
    cout<<res;
}