Range Sum Query ໂດຍໃຊ້ Sparse Table


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ການໂຄສະນາເຜີຍແຜ່ Zoho
Array

ໃນການສອບຖາມຜົນລວມຂອງບັນຊີໂດຍໃຊ້ບັນຫາຕາຕະລາງທີ່ຫຍໍ້ພວກເຮົາມີ ຄຳ ຖາມທີ່ມີຂອບເຂດແລະໃຫ້ເລກເຕັມ array. ວຽກທີ່ໄດ້ຮັບແມ່ນເພື່ອຊອກຫາຜົນລວມຂອງ ຈຳ ນວນທັງ ໝົດ ທີ່ເຂົ້າມາໃນຂອບເຂດ.

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ:

ຮອດ [] = {1,4,6,8,2,5}

ການສອບຖາມ: {(0, 3), (2, 4), (1, 5)}

ຜົນໄດ້ຮັບ:

+19 16 25

ຄໍາອະທິບາຍ: ຜົນລວມຂອງຕົວຄູນທີ່ເຂົ້າມາໃນລະດັບ 0, 3 ລວມແມ່ນ 1 + 4 + 6 + 8 ແມ່ນ 19. ອີກເທື່ອ ໜຶ່ງ, ຜົນບວກຂອງຕົວຄູນທີ່ມາໃນລະດັບ 2, 4 ລວມແມ່ນ 6 + 8 + 2 ແມ່ນ 16. ຜົນລວມຂອງເລກເຕັມ ທີ່ມາໃນຂອບເຂດ 1, 5 ລວມແມ່ນ 4 + 6 + 8 + 2 + 5 ແມ່ນ 25.

Range Sum Query ໂດຍໃຊ້ Sparse Table

ລະບົບວິເຄາະ

  1. ສ້າງຕາຕະລາງທີ່ກະແຈກກະຈາຍໂດຍໃຊ້ຕາຕະລາງ 2d.
  2. ລອກແຖວຂອງແຖວແລະ ໝາຍ ທຸກແຖວຂອງ sparse_table ເພື່ອຈັດລຽງ [i].
  3. ລອກແຖວຂອງຮັງ, ແລະປັບປຸງຄ່າ sparse_table ເປັນຜົນລວມຂອງຕາຕະລາງທີ່ຫຍໍ້ຂອງຖັນກ່ອນ ໜ້າ ນີ້ແລະທີ່ sparse_table [i + 2 j-1 ] [j-1] ແລະເກັບມັນໄວ້ເພື່ອ sparse_table [i] [j].
  4. ສຳ ລັບການສອບຖາມແຕ່ລະຢ່າງເພື່ອແກ້ໄຂ, ພວກເຮົາໄດ້ຮັບເບື້ອງຊ້າຍແລະຂວາ, ກຳ ນົດຄ່າຂອງຜົນຜະລິດໃຫ້ເປັນ 0.
  5. ລອກເອົາອາເລຈາກ 16 ຫາ 0, ແລະກວດເບິ່ງວ່າຊ້າຍ + 2j -1 ແມ່ນ ໜ້ອຍ ກ່ວາເທົ່າກັບສິດ, ຖ້າຖືກ,
    1. ເພີ່ມຄ່າຂອງຜົນຜະລິດເຂົ້າໃນ sparse_table [ຊ້າຍ] [j] ແລະເກັບຄ່າລວມເຂົ້າໃນຜົນຜະລິດ.
    2. ປັບປຸງຄ່າຂອງຊ້າຍຫາຊ້າຍ + 2
  6. ສົ່ງຄືນຄ່າຂອງຜົນຜະລິດ.

ຄໍາອະທິບາຍສໍາລັບ Range Sum Query ໂດຍໃຊ້ Sparse Table

ໄດ້ຮັບແຖວແລະແບບສອບຖາມ. ຊອກຫາຜົນລວມຂອງ ຈຳ ນວນທັງ ໝົດ ທີ່ເຂົ້າມາພາຍໃນຊ່ວງຂອງ ຄຳ ຖາມ. ພວກເຮົາຈະ ນຳ ໃຊ້ແນວຄິດຕາຕະລາງທີ່ກະແຈກກະຈາຍ. ພວກເຮົາຈະສ້າງໂຕະທີ່ກະແຈກກະຈາຍ. ຕາຕະລາງທີ່ຫົດຕົວແມ່ນຕາຕະລາງ 2d ເຊິ່ງພວກເຮົາຈະປະຕິບັດວຽກງານບາງຢ່າງແລະເກັບຮັກສາຄ່າຕ່າງໆໄວ້ໃນຕາຕະລາງທີ່ກະແຈກກະຈາຍ.

ປະກາດ 2d matrix. ພວກເຮົາໄດ້ ກຳ ນົດຂອບເຂດ ຈຳ ກັດ ໜຶ່ງ ຖ້ຽວແຖວແລະສູງສຸດ 16 ຖັນຕໍ່ແຖວ. ໂດຍສະເພາະພວກເຮົາເອົາເລກທີ 16 ຢູ່ທີ່ນີ້ເພາະວ່າຫລັງຈາກນັ້ນພວກເຮົາຈະໄດ້ເລກທີ່ໃຫຍ່ກວ່າ 2 ຍົກມາເປັນ 5, ດັ່ງນັ້ນ 16 ກໍ່ພໍ ຫຼັງຈາກນັ້ນ, ຫລັງຈາກນັ້ນຈະກ້າວສູ່ຂັ້ນຕອນ ທຳ ອິດຂອງການກໍ່ສ້າງໂຕະຕັ່ງ. ພວກເຮົາ ກຳ ລັງຈະ ໝາຍ ຫລືປັບປຸງຄ່າຕ່າງໆທີ່ຕາຕະລາງທີ່ຫົດຕົວເປັນສ່ວນປະກອບຂອງອາເລໃນຂະນະທີ່ ກຳ ລັງຜ່ານແຖວ. ຫຼັງຈາກນັ້ນຮັງພວກເຮົາ ກຳ ລັງກ້າວຂ້າມອາເລ, ອີກເທື່ອ ໜຶ່ງ ເຖິງ ຈຳ ນວນແຖວຂອງ k. ປັບປຸງຕາຕະລາງ sparse ທີ່ i, j ເປັນຜົນລວມຂອງຕາຕະລາງ sparse ທີ່ i, j-1 ແລະຕາຕະລາງ sparse ທີ່ i + 2j-1, j-1. ນີ້ຈະເປັນການປັບປຸງສຸດທ້າຍທີ່ຕ້ອງການ ສຳ ລັບຕາຕະລາງທີ່ຫຍໍ້.

ສຳ ລັບການສອບຖາມແຕ່ລະອັນທີ່ໃຫ້ຢູ່ເບື້ອງຊ້າຍ, ຊ່ວງຂວາມື, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຂ້າມອາເລ, ແຕ່ກ່ອນນັ້ນຈະ ກຳ ນົດຄ່າຂອງຜົນຜະລິດໃຫ້ເປັນ 0. ລົບລ້າງອາເລຈາກ 16 ເຖິງ 0, ເພື່ອວ່າພວກເຮົາຈະໄດ້ຮັບ ອຳ ນາດໃນແງ່ 2, ແຕ່ລະຄັ້ງ 1 <

ການປະຕິບັດ

ໂປແກຼມ C ++ ສຳ ລັບ Range Sum Query ໂດຍໃຊ້ Sparse Table

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

ໂປແກຼມ Java ສຳ ລັບ Range Sum Query ໂດຍໃຊ້ Sparse Table

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n * log (n)) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n * log (n)) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ກະສານອ້າງອີງ