CODEWITHSUNDEEP
arraysalgorithmdata-structures
sudoer
sudoer

Reputation: 195

Find product of integers at interval of X and update value at position 'i' in an array for N queries

I have given an array of integers of length up to 10^5 & I want to do following operation on array.

1-> Update value of array at any position i . (1 <= i <= n)

2-> Get products of number at indexes 0, X, 2X, 3X, 4X.... (J * X <= n)

Number of operation will be up to 10^5.

Is there any log n approach to answer query and update values.

Upvotes: 1

Views: 365

Answers (1)

shole
shole

Reputation: 4094

(Original thought is to use Segment Tree but I think that it is not needed...)

Let N = 10^5, A:= original array of size N

We use 0-based notation when we saying indexing below

Make a new array B of integers which of length up to M = NlgN :

First integer is equal to A[0];

Next N integers is of index 1,2,3...N of A; I call it group 1

Next N/2 integers is of index 2,4,6....; I call it group 2

Next N/3 integers 3,6,9.... I call it group 3

Here is an example of visualized B:

B = [A[0] | A[1], A[2], A[3], A[4] | A[2], A[4] | A[3] | A[4]]

I think the original thoughts can be used without even using Segment Tree.. (It is overkill when you think for operation 2, we always will query specific range on B instead of any range, i.e. we do not need that much flexibility and complexity to maintain the data structure)

You can create the new array B described above, also create another array C of length M, C[i] := products of Group i

For operation 1 simply use O(# factors of i) to see which Group(s) you need to update, and update the values in both B and C (i.e. C[x]/old B[y] *new B[y])

For operation 2 just output corresponding C[i]

Not sure if I was wrong but this should be even faster and should pass the judge, if the original idea is correct but got TLE

As OP has added a new condition: for operation 2, we need to multiply A[0] as well, so we can special handle it. Here is my thought:

Just declare a new variable z = A[0], for operation 1, if it is updating index 0, update this variable; for operation 2, query using the same method above, and multiply by z afterwards.

I have updated my answer so now I simply use the first element of B to represent A[0]

Example

A = {1,4,6,2,8,7}


B = {1 | 4,6,2,8,7 | 6,8 | 2 | 8 | 7 }  // O(N lg N)


C = {1 | 2688 | 48 | 2 | 8 | 7 } // O (Nlg N)

factorization for all possible index X (X is the index, so <= N) // O(N*sqrt(N)) 


opeartion 1:

update A[4] to 5: factors = 1,2,4  // Number of factors of index, ~ O(sqrt(N))
which means update Group 1,2,4   i.e. the corresponding elements in B & C

to locate the corresponding elements in B & C maybe a bit tricky, 
but that should not increase the complexity

B = {1 | 4,6,2,5,7 | 6,5 | 2 | 5 | 7 }    // O(sqrt(N))
C = {1 | 2688 | 48/8*5 | 2 | 8/8*5 | 7 }  // O(sqrt(N))


update A[0] to 2:
B = {2 | 4,6,2,5,7 | 6,5 | 2 | 5 | 7 }  // O(1)
C = {2 | 2688/8*5 | 48/8*5 | 2 | 8/8*5 | 7 }  // O(1)



// Now A is actually {2,4,6,2,5,7}

operation 2:

X = 3
C[3] * C[0] = 2*2 = 4  // O(1)


X = 2
C[2] * C[0] = 30*2 = 60  // O(1)

Upvotes: 1

Related Questions