MOD ์ฐ์ฐ ๋๋ฌธ์ ๋ง์ ์ํ์ฐฉ์ค๊ฐ ์์๋ค. ๊ฐ์ ์ ์ฅํ ๋์๋ MOD ์ฐ์ฐ ํ ์ ์ฅํ์ง ์๊ณ , ๊ณฑํ ๊ฐ์ ๊ตฌํ๊ฑฐ๋ ์ ์ฅํ ๋์๋ง MOD ์ฐ์ฐ์ ํด์ฃผ๋ ์ฌ๋ฐ๋ฅธ ํด๋ต์ด ๋์๋ค.
MOD ์ฐ์ฐ ๊ด๋ จํ์ฌ ์ฌ๋ฌ ์๋ฃ๋ค์ ์ฐพ์๋ณด๋ค๊ฐ ๋งจ ์ฒ์์ ๋ฐ์ ์์ด์ ํ ๋ฒ์ tree์ ์ ์ฅํ๋ makeTree ๋ฉ์๋๋ฅผ ์ ์ธํ์ง ์๊ณ update ๋ฉ์๋๋ก ๋์ฒดํ๋ ์ฝ๋๋ฅผ ๋ณด๊ฒ ๋์๋ค. ๊ทธ๋ ๊ฒ ์ฝ๋๋ฅผ ์์ฑํ๋ฉด ์๊ฐ ํจ์จ์ด ๋จ์ด์ง์ง ์์๊น, ์๊ฐํ๋๋ฐ ์ญ์๋์๋ค. ํ๋์ ์์ ๋ํ์ฌ update๋ฅผ ์ผ์ผ์ด ํ๋ ๊ฒ๋ณด๋ค, arr๋ฅผ ๋ฐ์์ ํ ๋ฒ์ ๋ฃ๋ ๊ฒ์ด ๋ ํจ์จ์ ์ด๋ค. ์์ธ์ง๋ ์ฝ๋๋ฅผ ๋ณด๋ฉด ์ ์ถํ ์ ์๋ค.
๋ฐ์ 744ms๊ฐ makeTree ๋์ update ๋ฉ์๋๋ฅผ ์ด ๊ฒฐ๊ณผ์ด๋ค.