ພິມແຖວທີ່ຖືກປັບປ່ຽນຫຼັງຈາກປະຕິບັດ ຄຳ ສັ່ງຂອງການເພີ່ມແລະການຫັກລົບ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ByteDance Cisco Citrix FreeCharge ແຮກເກີຣ ນາກາໂຣ Opera Teradata
Array

ທ່ານໄດ້ຮັບແຖວຂະ ໜາດ n, ໃນເບື້ອງຕົ້ນຄ່າທັງ ໝົດ ໃນອາເລຈະແມ່ນ 0, ແລະແບບສອບຖາມ. ການສອບຖາມແຕ່ລະອັນມີຄ່າ XNUMX ຢ່າງ, ປະເພດຂອງແບບສອບຖາມ T, ຈຸດຊ້າຍຂອງຊ່ວງ, ຈຸດທີ່ຖືກຕ້ອງຂອງຊ່ວງແລະຕົວເລກ k, ທ່ານຕ້ອງປະຕິບັດການ ດຳ ເນີນງານດັ່ງຕໍ່ໄປນີ້.

ຖ້າ T = 0, ເພີ່ມຄ່າ k ໃຫ້ກັບເລກເຕັມທັງ ໝົດ ພາຍໃນຂອບເຂດທີ່ໃຫ້ (ເລີ່ມຕົ້ນ, ສິ້ນສຸດ) ໃນແຖວທີ່ ກຳ ນົດໄວ້,

ຖ້າ T = 1, ຫັກລົບຄ່າ k ຈາກ ຈຳ ນວນທັງ ໝົດ ພາຍໃນຂອບເຂດທີ່ໃຫ້ (ເລີ່ມຕົ້ນ, ສິ້ນສຸດ) ໃນແຖວທີ່ ກຳ ນົດໄວ້,

ຍົກຕົວຢ່າງ

arr[]={0, 0, 0, 0, 0}
Query: {(0, 2, 4, 1), (1, 3, 5, 2), (0, 1, 4, 3)}
3 4 2 2 -2

ຄໍາອະທິບາຍ

(0, 2, 4, 1) ເພີ່ມ 1 ໃສ່ເລກເຕັມທັງ ໝົດ ພາຍໃນຂອບເຂດຍ້ອນວ່າມັນແມ່ນແບບສອບຖາມປະເພດ 0.

(1, 3, 5, 2) ຫັກ 2 ຈາກຕົວເລກທັງ ໝົດ ພາຍໃນຂອບເຂດຍ້ອນວ່າມັນແມ່ນແບບສອບຖາມປະເພດ 1.

(0, 1, 4, 3) ເພີ່ມ 3 ໃສ່ເລກເຕັມທັງ ໝົດ ພາຍໃນຂອບເຂດຍ້ອນວ່າມັນແມ່ນແບບສອບຖາມປະເພດ 0.

ພິມແຖວທີ່ຖືກປັບປ່ຽນຫຼັງຈາກປະຕິບັດ ຄຳ ສັ່ງຂອງການເພີ່ມແລະການຫັກລົບ

 

ສູດການຄິດໄລ່ເພື່ອພິມແຖວທີ່ຖືກປັບປ່ຽນຫຼັງຈາກການສອບຖາມຫຼາຍໆຄັ້ງ

  1. ເລີ່ມຕົ້ນ array ກັບ 0.
  2. ສຳ ລັບການສອບຖາມແຕ່ລະຢ່າງ,
  3. ຖ້າການສອບຖາມແບບປະເພດແມ່ນເພື່ອເພີ່ມຄ່າ, ຫຼັງຈາກນັ້ນໃຫ້ປັບປຸງຄ່າຢູ່ ຕຳ ແໜ່ງ ຊ້າຍ -1 ໂດຍການເພີ່ມຄ່າ k ແລະຢູ່ ຕຳ ແໜ່ງ ທີ່ຖືກຕ້ອງຈະຫັກຄ່າ k.
  4. ຖ້າການສອບຖາມແບບປະເພດແມ່ນການຫັກຄ່າ, ຫຼັງຈາກນັ້ນໃຫ້ປັບປຸງຄ່າຢູ່ ຕຳ ແໜ່ງ ຊ້າຍ -1 ໂດຍການຫັກລົບຄ່າ k ແລະຢູ່ ຕຳ ແໜ່ງ ທີ່ ເໝາະ ສົມເພີ່ມຄ່າ k.
  5. ລອກເອົາອາເລແລະເພີ່ມແຕ່ລະຄ່າທີ່ຜ່ານມາໃຫ້ກັບມູນຄ່າປະຈຸບັນຂອງອາເລ.
  6. ພິມຂບວນສຸດທ້າຍ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ຮັບອາເລ, ໃນເບື້ອງຕົ້ນ, ຄ່າທັງ ໝົດ ໃນອາເລແມ່ນ 0. ພວກເຮົາກໍ່ໄດ້ຖືກຈັດຫາດ້ວຍ a q ຈຳ ນວນຂອງແບບສອບຖາມ, ແບບສອບຖາມຈະມີສອງປະເພດ, ແຕ່ລະແບບແບບສອບຖາມ, ປະເພດຂອງມັນ, ລະດັບ, ແລະຕົວເລກ k. ຖ້າຫາກວ່າປະເພດຂອງການສອບຖາມແມ່ນ 0, ພວກເຮົາຈະເພີ່ມຄ່າ k ໃຫ້ກັບຕົວເລກທັງ ໝົດ ທີ່ເຂົ້າມາພາຍໃນຂອບເຂດ. ຖ້າພວກເຮົາໃຫ້ປະເພດ ຄຳ ຖາມເປັນ 1, ພວກເຮົາຈະຫັກຄ່າ k ຈາກຕົວເລກທັງ ໝົດ, ພາຍໃນຂອບເຂດ. ຫລັງຈາກປະຕິບັດການສອບຖາມທັງ ໝົດ ແລ້ວ, ພວກເຮົາຈະໄດ້ຮັບການພິມແບບນັ້ນ.

ສຳ ລັບການປະຕິບັດງານເຫຼົ່ານີ້. ທຳ ອິດພວກເຮົາ ຈຳ ເປັນຕ້ອງກວດສອບວ່າການສອບຖາມປະເພດໃດໃຫ້ພວກເຮົາ. ຖ້າການສອບຖາມມີປະເພດ ທຳ ອິດພວກເຮົາເພີ່ມຄ່າ k ໃສ່ຈຸດເລີ່ມຕົ້ນຂອງຊ່ວງໃນແຖວ. ພ້ອມກັນນີ້, ຫັກລົບຄ່າ k ຈາກຈຸດສິ້ນສຸດຂອງຂອບເຂດຂອງອາເລ.

ພວກເຮົາຈະເຮັດແນວໃດກົງກັນຂ້າມກັບເຕັກນິກທີ່ກ່າວມາກ່ອນ. ຖ້າພວກເຮົາຖືກມອບໃຫ້ໃຫ້ໃຊ້ແບບສອບຖາມປະເພດ 1 ເຊິ່ງພວກເຮົາຕ້ອງຫັກລົບຄ່າທັງ ໝົດ ຂອງຂບວນເລກເຕັມພາຍໃນຂອບເຂດ. ຈາກນັ້ນພວກເຮົາຈະຫັກລົບຄ່າ k ຈາກຄ່າເລີ່ມຕົ້ນຂອງອາເລ. ຫລັງຈາກນັ້ນ, ເພີ່ມຄ່າ k ຢູ່ໃນຈຸດສຸດທ້າຍຂອງລະດັບ.

ສຳ ລັບແຕ່ລະ ຄຳ ຖາມທີ່ໃຫ້. ພວກເຮົາຕ້ອງປະຕິບັດເຕັກນິກທີ່ກ່າວມານັ້ນ. ຫຼັງຈາກນັ້ນພວກເຮົາຈະ ກຳ ລັງສ້າງຂບວນການ, ເຊິ່ງໃນນັ້ນພວກເຮົາຈະເພີ່ມມູນຄ່າທີ່ຜ່ານມາໃຫ້ກັບມູນຄ່າປະຈຸບັນຂອງອາເລ. ແລະເກັບຮັກສາຜົນລວມເຂົ້າໃນມູນຄ່າປັດຈຸບັນ. ຫຼືພວກເຮົາສາມາດເວົ້າວ່າພວກເຮົາປັບປຸງມູນຄ່າປະຈຸບັນຂອງອາເລ. ຫລັງຈາກສ້າງອາເລນ, ພວກເຮົາຈະໄດ້ຮັບການພິມແຖວ. ນັ້ນຈະເປັນຜົນທີ່ຕ້ອງການຂອງອາເລທີ່ຖືກປ່ຽນແປງ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອພິມແຖວທີ່ຖືກປັບປ່ຽນຫຼັງຈາກປະຕິບັດ ຄຳ ສັ່ງຂອງການເພີ່ມແລະການຫັກລົບ

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

ລະຫັດ Java ເພື່ອພິມແຖວທີ່ຖືກປັບປ່ຽນຫຼັງຈາກປະຕິບັດ ຄຳ ສັ່ງຂອງການເພີ່ມແລະສ່ວນຫຼຸດ

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

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

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

O (q + n) ບ່ອນທີ່ "Q" ແມ່ນ ຈຳ ນວນ ຄຳ ຖາມແລະ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເພາະວ່າ ທຳ ອິດພວກເຮົາ ດຳ ເນີນການສອບຖາມ Q ເຊິ່ງໃຊ້ເວລາ O (1) ແລະຫຼັງຈາກນັ້ນກໍ່ສ້າງຂບວນຕ້ອງໃຊ້ເວລາ O (N).

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ສ້າງຂບວນການປະຕິບັດງານ. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.