ઉમેરો અને બાદબાકીના આદેશો ચલાવ્યા પછી સુધારેલા એરે છાપો  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ByteDance સિસ્કો સિટ્રીક્સ ફ્રીચાર્જ હેકરરંક નાગરો ઓપેરા તેરાદાતા
અરે

તમને કદ n ની એરે આપવામાં આવશે, શરૂઆતમાં એરેમાંના બધા મૂલ્યો 0, અને પ્રશ્નો હશે. દરેક ક્વેરીમાં ચાર મૂલ્યો, ક્વેરીના પ્રકાર ટી, રેંજનો ડાબું પોઇન્ટ, રેન્જનો જમણો પોઇન્ટ અને નંબર K હોય છે, તમારે નીચેની કામગીરી કરવી પડશે.

જો ટી = 0, આપેલ એરેમાં આપેલ શ્રેણી (પ્રારંભ, અંત) ની બધી પૂર્ણાંકોમાં વેલ્યુ કે ઉમેરો,

જો ટી = 1, આપેલ શ્રેણીમાં બધી પૂર્ણાંકોમાંથી મૂલ્ય કે બાદબાકી કરો (પ્રારંભ કરો, અંત) આપેલા એરેમાં,

ઉદાહરણ  

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. પ્રારંભ કરો એરે 0 સાથે.
  2. દરેક ક્વેરી માટે,
  3. જો પ્રકાર ક્વેરી કિંમતો ઉમેરવાની છે, તો પછી મૂલ્ય k ને ઉમેરીને ડાબી -1 સ્થિતિ પર મૂલ્યને અપડેટ કરો અને જમણી સ્થિતિ પર મૂલ્ય કે બાદબાકી કરો.
  4. જો પ્રકાર ક્વેરી કિંમતોને બાદબાકી કરવાની છે, તો પછી મૂલ્ય કે બાદબાકી કરીને ડાબી -1 સ્થિતિ પર મૂલ્યને અપડેટ કરો અને જમણી સ્થિતિ પર મૂલ્ય કેને ઉમેરો.
  5. એરેને પસાર કરો અને એરેના વર્તમાન મૂલ્યમાં દરેક પાછલું મૂલ્ય ઉમેરો.
  6. અંતિમ એરે છાપો.
આ પણ જુઓ
વિપરીત ક્રમમાં ફિબોનાકી નંબરો છાપો

સમજૂતી

આપણને એરે આપવામાં આવે છે, શરૂઆતમાં, એરેમાં બધા વેલ્યુ 0 છે. આપણને એ પણ આપવામાં આવે છે q ક્વેરીઝની સંખ્યા, ક્વેરી બે પ્રકારના હશે, દરેક ક્વેરી સમાવે છે, તેનો પ્રકાર, શ્રેણી અને નંબર કે. જો ક્વેરીનો પ્રકાર 0 છે, તો આપણે શ્રેણીમાં આવતા બધા પૂર્ણાંકોમાં વેલ્યુ કે ઉમેરીશું. જો આપણને ક્વેરીનો પ્રકાર 1 તરીકે આપવામાં આવે છે, તો આપણે શ્રેણીના બધા પૂર્ણાંકોમાંથી વેલ્યુ કે બાદબાકી કરીશું. બધી ક્વેરીઝ એક્ઝેક્યુટ કર્યા પછી, અમે તે પરિણામ એરે પ્રિન્ટ કરીશું.

આ કામગીરી કરવા માટે. પહેલા આપણે તપાસ કરવાની જરૂર છે કે અમને કયા પ્રકારનાં ક્વેરી આપવામાં આવે છે. જો ક્વેરી પ્રથમ પ્રકારની છે, તો પછી આપણે એરેમાં શ્રેણીના પ્રારંભિક બિંદુમાં વેલ્યુ કે ઉમેરીશું. પણ, એરેની શ્રેણીના અંતિમ બિંદુથી મૂલ્ય કે બાદબાકી કરો.

અમે અગાઉ ઉલ્લેખિત તકનીકની વિરુદ્ધ કરીશું. જો આપણને ટાઇપ 1 ક્વેરીનો ઉપયોગ કરવા માટે આપવામાં આવે છે જેમાં આપણે પૂર્ણાંક એરેના બધા મૂલ્યોને શ્રેણીમાં બાદ કરીશું. પછી આપણે એરેના પ્રારંભિક મૂલ્યથી વેલ્યુ કે બાદબાકી કરીશું. તે પછી, શ્રેણીના અંતિમ બિંદુ અનુક્રમણિકા પર મૂલ્ય કે ઉમેરો.

આપેલ દરેક પ્રશ્નો માટે. અમારે ઉલ્લેખિત તકનીક કરવી પડશે. પછી આપણે એરે બનાવીશું, જેમાં આપણે એરેના વર્તમાન મૂલ્યમાં પાછલા મૂલ્ય ઉમેરીશું. અને સરવાળો વર્તમાન મૂલ્યમાં સંગ્રહિત કરો. અથવા આપણે કહી શકીએ કે આપણે એરેનું વર્તમાન મૂલ્ય અપડેટ કરીએ છીએ. એરે બનાવ્યા પછી, આપણે એરે પ્રિન્ટ કરીશું. તે સુધારેલા એરેનું ઇચ્છિત પરિણામ હશે.

આ પણ જુઓ
મિત્રો જોડી બનાવવાની સમસ્યા

કોડ  

ઉમેરાઓ અને બાદબાકીના આદેશો ચલાવ્યા પછી સુધારેલા એરે છાપવા માટે સી ++ કોડ

#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

ઉમેરા અને બાદબાકીના આદેશો ચલાવ્યા પછી સુધારેલા એરે છાપવા માટે જાવા કોડ

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 (1) સમય લે છે અને પછી એરે બનાવવા માટે O (N) સમય જરૂરી છે.

આ પણ જુઓ
શબ્દમાળામાં નેસ્ટેડ પેરેંથેસિસની મહત્તમ Depંડાઈ શોધો

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. ત્યારબાદ અમે performપરેશંસ કરવા માટે એક એરે બનાવી છે. જગ્યાની જટિલતા રેખીય છે.