ਇੱਕ ਬਾਇਨਰੀ ਐਰੇ ਤੇ ਪ੍ਰਸ਼ਨ ਗਿਣੋ ਅਤੇ ਬਦਲੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਫੇਸਬੁੱਕ ਗੂਗਲ ਉਬੇਰ
ਅਰੇ ਖੰਡ-ਰੁੱਖ

An ਐਰੇ ਸਾਈਜ਼ n ਨੂੰ ਇਨਪੁਟ ਵੈਲਯੂ ਵਜੋਂ ਦਿੱਤਾ ਗਿਆ ਹੈ. ਸਮੱਸਿਆ "ਬਾਇਨਰੀ ਐਰੇ 'ਤੇ ਕਾਉਂਟ ਅਤੇ ਟੌਗਲ ਪੁੱਛਗਿੱਛ" ਕੁਝ ਪ੍ਰਸ਼ਨਾਂ ਨੂੰ ਕਰਨ ਲਈ ਕਹਿੰਦੀ ਹੈ ਜਿਹੜੀਆਂ ਹੇਠਾਂ ਦਿੱਤੀਆਂ ਗਈਆਂ ਹਨ, ਬੇਨਤੀਆਂ ਇੱਕ ਬੇਤਰਤੀਬੇ varyੰਗ ਨਾਲ ਬਦਲ ਸਕਦੀਆਂ ਹਨ.

ਸਵਾਲ ਹਨ ⇒

ਟੌਗਲ ਕਿ queryਰੀ ⇒ ਟੌਗਲ (ਸ਼ੁਰੂਆਤ, ਅੰਤ), ਇਸ ਟੌਗਲ ਪੁੱਛਗਿੱਛ ਦਾ ਅਰਥ ਹੈ, ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰ 0 ਨੂੰ 1 ਜਾਂ 1s ਵਿੱਚ 0 ਸਕਿੰਟ ਵਿੱਚ ਬਦਲੋ.

ਗਿਣਤੀ ਪੁੱਛਗਿੱਛ ⇒ ਗਿਣਤੀ (ਅਰੰਭ, ਅੰਤ), ਇਸ ਗਿਣਤੀ ਪੁੱਛਗਿੱਛ ਦਾ ਅਰਥ ਹੈ ਕਿ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰਲੇ ਸਮੂਹਾਂ ਦੀ ਗਿਣਤੀ ਕਰਨਾ.

ਉਦਾਹਰਨ

n = 5
toggle(0, 1)
toggle(2, 3)
count(1, 2)
toggle(1, 4)
count(0, 2)
Count of all the ones within the range 1 and 2 is 2.
The count of all the ones within the range 0 and 2 is 1.

ਸਪਸ਼ਟੀਕਰਨ: ਹਰੇਕ ਕਾ queryਂਟ ਪ੍ਰਸ਼ਨ ਤੇ ਇੱਕ ਦੀ ਗਿਣਤੀ ਛਾਪੀ ਜਾਂਦੀ ਹੈ.

ਇੱਕ ਬਾਇਨਰੀ ਐਰੇ ਤੇ ਪ੍ਰਸ਼ਨ ਗਿਣੋ ਅਤੇ ਬਦਲੋ

ਐਲਗੋਰਿਥਮ

  1. ਚੈੱਕ ਕਰੋ ਕਿ ਬੂਲੀਅਨ boolTree ਸੱਚ ਹੈ ਜਾਂ ਗਲਤ ਹੈ. ਜੇ ਇਹ ਸਹੀ ਹੈ ਤਾਂ ਉਸ ਨੋਡ ਨੂੰ ਗਲਤ ਵਜੋਂ ਮਾਰਕ ਕਰੋ. ਵਿੱਚ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰੋ ਖੰਡ ਅੰਤ ਦੇ ਤੌਰ ਤੇ - +1 ਖੰਡ ਟ੍ਰੀ [ਨੋਡ] ਸ਼ੁਰੂ ਕਰਨਾ.
  2. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਇਹ ਇਕ ਪੱਤਾ ਨੋਡ ਨਹੀਂ ਹੈ, ਫਿਰ ਇਸ ਦੀ ਕੀਮਤ ਨੂੰ ਸੈੱਟ ਜਾਂ ਉਲਟ ਕਰੋ boolTree ਬੱਚਿਆਂ ਦੀ
  3. ਜੇ ਮੁੱਲ ਸੀਮਾ ਤੋਂ ਬਾਹਰ ਹਨ, ਤਾਂ ਵਾਪਸ ਜਾਓ.
  4. ਚੈੱਕ ਕਰੋ ਜੇ ਖੰਡ ਰੇਂਜ ਵਿੱਚ ਆਉ, ਜੇ ਸੱਚ ਹੈ, ਤਾਂ ਖੰਡ ਦੇ ਦਰਜਾ ਦੇ ਮੌਜੂਦਾ ਮੌਜੂਦਾ ਤੱਤ ਨੂੰ ਅੰਤਰ ਦੇ ਤੌਰ ਤੇ ਅਪਡੇਟ ਕਰੋ ਅਤੇ ਦੁਬਾਰਾ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਇਹ ਪੱਤਾ ਨੋਡ ਨਹੀਂ ਹੈ, ਅਤੇ ਉਹੀ ਵਿਧੀ ਕਰੋ ਜਿਵੇਂ ਕਦਮ 2 ਵਿੱਚ ਹੈ.
  5. ਜਾਂਚ ਕਰੋ ਕਿ ਜੇ ਖੰਡ ਟ੍ਰੀ ਸੀਮਾ ਵਿੱਚ ਨਹੀਂ ਹੈ ਅਤੇ ਖੰਡ ਦੇ ਟ੍ਰੀ ਦੇ ਦੋਵੇਂ ਪਾਸੇ ਮੁੱਲ ਲਪੇਟ ਹੋ ਰਹੇ ਹਨ ਤਾਂ ਮੁੜ ਕਾਲ ਕਰੋ.
  6. ਸੈਗਮੈਂਟਟ੍ਰੀ ਨੋਡ ਦੇ ਮੌਜੂਦਾ ਨੋਡ ਦਾ ਮੁੱਲ ਆਪਣੇ ਬੱਚਿਆਂ ਦੇ ਨਤੀਜੇ ਵਜੋਂ ਅਪਡੇਟ ਕਰੋ.

ਗਿਣਤੀ ਪੁੱਛਗਿੱਛ ਲਈ

  1. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਮੌਜੂਦਾ ਨੋਡ ਸੀਮਾ ਤੋਂ ਬਾਹਰ ਹੈ, ਫਿਰ 0 ਵਾਪਸ ਕਰੋ.
  2. ਫਿਰ ਵੇਖੋ ਕਿ ਕੀ ਬੂਲਟ੍ਰੀਜ਼ ਦਾ ਮੌਜੂਦਾ ਨੋਡ ਸਹੀ ਹੈ, ਜੇ ਸਹੀ ਹੈ, ਤਾਂ ਬੋਲਟ ਟ੍ਰੀਜ਼ ਦੇ ਮੌਜੂਦਾ ਨੋਡ ਨੂੰ ਗਲਤ ਤੇ ਨਿਸ਼ਾਨ ਲਗਾਓ ਅਤੇ ਸੈਗਮੈਂਟਟ੍ਰੀ ਦੇ ਮੌਜੂਦਾ ਨੋਡ ਵੈਲਯੂ ਨੂੰ ਫਰਕ ਵਜੋਂ ਅਪਡੇਟ ਕਰੋ.
  3. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਇਹ ਇਕ ਪੱਤਾ ਨੋਡ ਨਹੀਂ ਹੈ ਅਤੇ ਬੱਚਿਆਂ ਦੇ ਮੁੱਲਾਂ ਨੂੰ ਉਲਟਾ ਦੇਵੇਗਾ.
  4. ਜਾਂਚ ਕਰੋ ਕਿ ਜੇ ਖੰਡ ਦਿੱਤਾ ਗਿਆ ਸੀਮਾ ਵਿਚ ਹੈ, ਤਾਂ ਖੰਡ ਟ੍ਰੀ [ਨੋਡ] ਵਾਪਸ ਕਰੋ.
  5. ਜੇ ਨਹੀਂ ਤਾਂ ਫਿਰ ਫੰਕਸ਼ਨ ਨੂੰ ਲਗਾਤਾਰ ਕਾਲ ਕਰੋ ਤਾਂ ਕਿ ਇਹ ਓਵਰਲੈਪ ਨਾ ਹੋ ਜਾਵੇ.

ਕਥਾ

ਅਸੀਂ ਐਨੇ ਦੀ ਇਕ ਐਰੇ ਦਿੱਤੀ ਹੈ ਕਿ ਇਸ ਦੀਆਂ ਸਾਰੀਆਂ ਵੈਲਿ 0.ਜ਼ ਨੂੰ 0 ਤੋਂ ਸ਼ੁਰੂ ਕਰ ਦਿੱਤਾ ਗਿਆ ਹੈ. ਅਸੀਂ ਦੋ ਪੁੱਛਗਿੱਛਾਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਜੋ ਕਿ ਟੌਗਲ ਪੁੱਛਗਿੱਛ ਹਨ ਜੋ ਸਾਰੇ 1 ਨੂੰ 1s ਵਿਚ ਅਤੇ ਸਾਰੇ 0 ਨੂੰ 0s ਵਿਚ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰ ਬਦਲਣਾ ਹੈ. . ਗਿਣਤੀ ਪੁੱਛਗਿੱਛ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਦੇ ਅੰਦਰ ਮੌਜੂਦ ਸਾਰੇ ਜ਼ੀਰੋ ਨੂੰ ਗਿਣਨਾ ਹੈ. ਅਸੀਂ ਸੇਗਮੈਂਟਟ੍ਰੀ ਦੀ ਵਰਤੋਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਜੋ ਕਿ 1 ਦੇ ਤੌਰ ਤੇ ਅਰੰਭ ਕੀਤੀ ਗਈ ਹੈ. ਸੋ ਅਸੀਂ ਇਸਨੂੰ ਸੀਮਾ ਦੇ ਅੰਦਰ XNUMXs ਵਿੱਚ ਬਦਲਦੇ ਹਾਂ.

ਜਦੋਂ ਵੀ ਟੌਗਲ ਫੰਕਸ਼ਨ ਨੂੰ ਬੁਲਾਇਆ ਜਾਂਦਾ ਹੈ, ਅਸੀਂ ਬੁਲੀਅਨ ਐਰੇ ਦੀ ਭਾਲ ਕਰਾਂਗੇ ਜੋ ਅਸੀਂ ਬੂਲਟ੍ਰੀ ਦੇ ਰੂਪ ਵਿੱਚ ਬਣਾਏ ਸਨ ਜੋ ਕਿ ਗਲਤ ਵਜੋਂ ਅਰੰਭ ਕੀਤਾ ਗਿਆ ਸੀ, ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੀ ਬੋਲਟ੍ਰੀ ਦਾ ਮੌਜੂਦਾ ਨੋਡ ਵੈਲਯੂ ਸਹੀ ਹੈ ਜਾਂ ਗਲਤ, ਜੇ ਇਹ ਗਲਤ ਹੈ ਤਾਂ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਕਿਸੇ ਵੀ ਅਪਡੇਟ ਵਿੱਚ ਹੈ. ਹੁਣ ਤੱਕ ਨਹੀਂ ਕੀਤਾ ਗਿਆ. ਇਸ ਲਈ ਸਾਨੂੰ ਇਹ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਅਤੇ ਜੇ ਇਹ ਸੱਚ ਹੈ ਤਾਂ ਸਭ ਤੋਂ ਪਹਿਲਾਂ, ਅਸੀਂ ਇਸਨੂੰ ਗਲਤ ਨਿਸ਼ਾਨਦੇਹੀ ਕਰਦੇ ਹਾਂ, ਇਸ ਲਈ ਅਸੀਂ ਇਸਨੂੰ ਬਾਅਦ ਵਿਚ ਇਸਤੇਮਾਲ ਕਰ ਸਕਦੇ ਹਾਂ, ਅਤੇ ਮੌਜੂਦਾ ਨੋਡ 'ਤੇ ਸੈਗਮੈਂਟਟ੍ਰੀ ਦੇ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰਨ ਅਤੇ ਅਰੰਭ ਕਰਨ ਦੇ ਅੰਤਰ ਦੇ ਜੋੜ ਵਜੋਂ ਅਪਡੇਟ ਕਰ ਸਕਦੇ ਹਾਂ. 1 ਅਤੇ ਮੌਜੂਦਾ ਨੋਡ ਦੇ ਸੇਗਮੈਂਟਟ੍ਰੀ ਦੇ ਮੁੱਲ ਦਾ ਅੰਤਰ. ਅਸੀਂ ਇਸਦੀ ਜਾਂਚ ਕਰ ਰਹੇ ਹਾਂ ਕਿ ਕੀ ਇਹ ਪੱਤਾ ਨੋਡ ਨਹੀਂ ਹੈ, ਕਿਉਂਕਿ ਜੇ ਇਹ ਹੈ, ਤਾਂ ਅਸੀਂ ਉਸ ਤੋਂ ਬਾਅਦ ਓਪਰੇਸ਼ਨ ਨਹੀਂ ਕਰਾਂਗੇ. ਜੇ ਇਹ ਨਹੀਂ ਹੈ, ਤਾਂ ਅਸੀਂ ਬੱਚਿਆਂ ਦੇ ਨੋਡ ਦੇ ਮੁੱਲਾਂ ਨੂੰ ਬੁਲੀਅਨ ਦੇ ਮੁੱਲਾਂ ਦੇ ਰੂਪ ਵਿੱਚ ਅਪਡੇਟ ਕਰਾਂਗੇ.

ਜਾਂਚ ਕਰੋ ਕਿ ਸੈਗਮੈਂਟਟ੍ਰੀ ਦਾ ਮੌਜੂਦਾ ਖੰਡ ਕਿਸੇ ਨਿਰਧਾਰਤ ਸੀਮਾ ਦੇ ਅੰਦਰ ਹੈ ਜਾਂ ਨਹੀਂ. ਜੇ ਨਹੀਂ ਤਾਂ ਫਿਰ ਲਈ ਅਜਿਹੀਆਂ ਲਗਾਤਾਰ ਕਾਲਾਂ ਕਰੋ ਕਿ ਨੋਡਸ ਦਾ ਖੰਡ ਦਿੱਤਾ ਗਿਆ ਸੀਮਾ ਦੇ ਅੰਦਰ ਆ.

ਉਹੀ ਕੰਮ ਕਾਉਂਟੀ ਫੰਕਸ਼ਨ ਨਾਲ ਕਰਨਾ ਹੈ ਪਰ ਥੋੜ੍ਹੀ ਜਿਹੀ ਵੱਖਰੀ ਪਹੁੰਚ ਨਾਲ. ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਮੌਜੂਦਾ ਨੋਡ ਸੀਮਾ ਤੋਂ ਬਾਹਰ ਨਹੀਂ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਜੇ ਇਹ ਫਿਰ ਅਸਾਨੀ ਨਾਲ 0 ਦਾ ਮੁੱਲ ਵਾਪਸ ਕਰਦਾ ਹੈ.

ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਮੌਜੂਦਾ ਨੋਡ ਨੂੰ ਹਿੱਸੇ ਦੇ ਟ੍ਰੀ ਦੇ ਮੌਜੂਦਾ ਨੋਡ ਨਾਲ ਨਹੀਂ ਦਰਸਾਉਣਾ ਚਾਹੀਦਾ ਹੈ. ਜੇ ਸਹੀ ਹੈ ਤਾਂ ਮੌਜੂਦਾ ਨੋਡ ਨੂੰ ਗਲਤ ਵਜੋਂ ਅਪਡੇਟ ਕਰੋ, ਅਤੇ ਸੈਗਮੈਂਟਟ੍ਰੀ ਦੇ ਮੌਜੂਦਾ ਨੋਡ ਦੇ ਮੁੱਲਾਂ ਨੂੰ ਅਪਗਰੇਡ ਕਰਨ ਅਤੇ ਅਰੰਭ ਕਰਨ ਦੇ ਅੰਤਰ ਦੇ ਜੋੜ ਵਜੋਂ ਅਤੇ ਸੀਜਮੈਂਟ ਟ੍ਰੀ ਦੇ 1 ਅਤੇ ਮੌਜੂਦਾ ਨੋਡ ਦੇ ਅੰਤਰ ਦੇ ਜੋੜ ਵਜੋਂ ਜੋ ਅਸੀਂ ਟੌਗਲਿੰਗ ਫੰਕਸ਼ਨ ਵਿਚ ਕੀਤੇ ਹਨ, ਦੁਬਾਰਾ ਜਾਂਚ ਕਰਨਾ ਇਹ ਹੈ ਕੋਈ ਪੱਤਾ ਨਹੀਂ, ਫਿਰ ਬੱਚਿਆਂ ਦੇ ਨੋਡਾਂ ਦੇ ਅਪਡੇਸ਼ਨ ਨਾਲ ਅੱਗੇ ਵਧੋ. ਹੁਣ ਤੱਕ ਇਸ ਬਿੰਦੂ ਤੇ, ਅਸੀਂ ਜਵਾਬ ਵਾਪਸ ਕਰਨ ਲਈ ਸਾਰੇ ਪੂਰਵ-ਜ਼ਰੂਰੀ didੰਗਾਂ ਨੂੰ ਕੀਤਾ, ਇਸਦੇ ਲਈ ਅਸੀਂ ਇਹ ਵੇਖਣ ਜਾ ਰਹੇ ਹਾਂ ਕਿ ਕੀ ਨੋਡਾਂ ਦਾ ਮੌਜੂਦਾ ਖੰਡ ਦਿੱਤਾ ਗਿਆ ਸੀਮਾ ਦੇ ਅੰਦਰ ਹੈ ਜਾਂ ਨਹੀਂ ਅਤੇ ਸੀਗਮੈਂਟਟ੍ਰੀ ਨੋਡ ਦਾ ਮੌਜੂਦਾ ਮੁੱਲ ਵਾਪਸ ਕਰ ਦੇਵੇਗਾ. ਹੋਰ ਤਾਂ ਇਸ ਨੂੰ ਸੀਮਾ ਦੇ ਅੰਦਰ ਕਰਨ ਲਈ ਫੰਕਸ਼ਨ ਨੂੰ ਲਗਾਤਾਰ ਕਾਲ ਕਰਦਾ ਹੈ.

ਲਾਗੂ

ਬਾਇਨਰੀ ਐਰੇ 'ਤੇ ਕਾ Countਂਟਸ ਅਤੇ ਟੌਗਲ ਪੁੱਛਗਿੱਛ ਲਈ ਸੀ ++ ਕੋਡ

#include<iostream>
using namespace std;

const int MAX = 100000;

int segmentTree[MAX] = {0};

bool boolTree[MAX] = {false};

void toggle(int node, int starting, int ending, int rangeStart, int rangeEnding)
{
    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending - starting + 1 - segmentTree[node];

        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
    }
    if (starting>ending || rangeStart > ending || rangeEnding < starting)
        return ;
    if (rangeStart<=starting && ending<=rangeEnding)
    {
        segmentTree[node] = ending-starting+1 - segmentTree[node];
        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
        return;
    }
    int mid = (starting+ending)/2;
    toggle((node<<1), starting, mid, rangeStart, rangeEnding);
    toggle((node<<1)+1, mid+1,ending, rangeStart, rangeEnding);
    if (starting < ending)
        segmentTree[node] = segmentTree[node<<1] + segmentTree[(node<<1)+1];
}

int count(int node, int starting, int ending, int qs, int qe)
{
    if (starting>ending || qs > ending || qe < starting)
        return 0;

    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending-starting+1-segmentTree[node];

        if (starting<ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[(node<<1)+1] = !boolTree[(node<<1)+1];
        }
    }
    if (qs<=starting && ending<=qe)
        return segmentTree[node];

    int mid = (starting+ending)/2;
    return count((node<<1), starting, mid, qs, qe) +
           count((node<<1)+1, mid+1, ending, qs, qe);
}

int main()
{
    int n = 5;
    toggle(1, 0, n-1, 0, 1);
    toggle(1, 0, n-1, 2, 3);
    cout << count(1, 0, n-1, 1, 2) << endl;
    toggle(1, 0, n-1, 1, 4);
    cout << count(1, 0, n-1, 0, 2) << endl;

    return 0;
}
2
1

ਜਾਵਾ ਕੋਡ ਨੂੰ ਗਿਣਨ ਲਈ ਅਤੇ ਇਕ ਬਾਈਨਰੀ ਐਰੇ ਤੇ ਪੁੱਛਗਿੱਛ ਬਦਲੋ

class toggleAndCount
{
    static final int MAX = 100000;

    static int segmentTree[] = new int[MAX];

    static boolean boolTree[] = new boolean[MAX];

    static void toggle(int node, int starting,int ending, int rangeStart, int rangeEnding)
    {
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
        }
        if (starting > ending || rangeStart > ending || rangeEnding < starting)
        {
            return;
        }
        if (rangeStart <= starting && ending <= rangeEnding)
        {
            segmentTree[node] = ending - starting + 1 - segmentTree[node];
            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
            return;
        }

        int mid = (starting + ending) / 2;
        toggle((node << 1), starting, mid, rangeStart, rangeEnding);
        toggle((node << 1) + 1, mid + 1, ending, rangeStart, rangeEnding);
        if (starting < ending)
        {
            segmentTree[node] = segmentTree[node << 1] +segmentTree[(node << 1) + 1];
        }
    }
    static int count(int node, int starting,int ending, int qs, int qe)
    {
        if (starting > ending || qs > ending || qe < starting)
        {
            return 0;
        }
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[(node << 1) + 1] = !boolTree[(node << 1) + 1];
            }
        }
        if (qs <= starting && ending <= qe)
        {
            return segmentTree[node];
        }
        int mid = (starting + ending) / 2;
        return count((node << 1), starting, mid, qs, qe) + count((node << 1) + 1, mid + 1, ending, qs, qe);
    }
    public static void main(String args[])
    {
        int n = 5;

        toggle(1, 0, n-1, 0, 1);
        toggle(1, 0, n-1, 2, 3);
        System.out.println( count(1, 0, n-1, 1, 2));
        toggle(1, 0, n-1, 1, 4);
        System.out.println(count(1, 0, n-1, 0, 2));
    }
}

2
1

ਬਾਇਨਰੀ ਐਰੇ 'ਤੇ ਕਾਉਂਟ ਅਤੇ ਟੌਗਲ ਪੁੱਛਗਿੱਛ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਕਿਯੂ ਲੌਗ ਐਨ) ਜਿੱਥੇ ਕਿ "Q" ਕਿeriesਰੀਆਂ ਦੀ ਗਿਣਤੀ ਹੈ ਅਤੇ “ਐਨ” ਐਰੇ ਦਾ ਆਕਾਰ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਦਾ ਆਕਾਰ ਹੈ.

ਹਵਾਲਾ