๊ตฌ๊ฐํธ๋ฆฌ(Segment Tree)๋? ๊ตฌ๊ฐํธ๋ฆฌ๋ ํน์ ๊ตฌ๊ฐ์์ ํน์ ํ ๊ฐ์ ๋ฝ์์ฌ ๋ ์ ์ฉํ๊ฒ ์ฌ์ฉ. ์ธ๊ทธ๋จผํธ ํธ๋ฆฌ๋ผ๊ณ ๋ ํ๋ค.
1) ๋ฐฐ์ด ์ด๊ธฐํ
2) ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ
์ ํ์ ์ผ๋ก ๊ตฌ๊ฐ ํฉ์ ๊ตฌํ๋ ๊ณผ์ ์
๐(๐)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค
๐(๐๐๐๐)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค1) ์์ ์ด์ง ํธ๋ฆฌ์ ๋ฐ์ดํฐ ์ฝ์
2) ๊ตฌ๊ฐ ํฉ ํธ๋ฆฌ ์์ฑ
๋ฃจํธ
๋ ์ธ๋ฑ์ค 1๋ถํฐ ์์. ๋ฃจํธ๋ ์ ์ฒด ๋ฐ์ดํฐ์ธ 0~6๊น์ง ์ธ๋ฑ์ค์ ๋ชจ๋ ๋ฐ์ดํฐ์ ํฉ๋ฃจํธ
์ ์ผ์ชฝ ์์์ ์ธ๋ฑ์ค 0~3๊น์ง์ ๋ฐ์ดํฐ ํฉ๋ฃจํธ
์ ์ค๋ฅธ์ชฝ ์์์ ์ธ๋ฑ์ค 4~6๊น์ง์ ๋ฐ์ดํฐ ํฉ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ๋ฉด์ ํ์ฌ ๊ฐ์ง๊ณ ์๋ ๊ตฌ๊ฐ์ ๋ํ ์ ๋ณด๋ฅผ ๋ฐ์ผ๋ก ๋๋๊ณ , ์ด ์ ๋ณด๋ฅผ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์์ผ๋ก ์ ๋ฌํด์ ๊ฐ์ ๊ตฌํ๋ค
3) ์์ฑ
๐(๐๐๐๐)
์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค์๊ฐ๋ณต์ก๋: ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ๊ณผ ์ ๋ ฅ์ ํจ์ ๊ด๊ณ.
์ปดํจํฐ๊ณผํ์์ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ๋ณต์ก๋๋ ์ ๋ ฅ์ ๋ํ๋ด๋ ๋ฌธ์์ด ๊ธธ์ด์ ํจ์๋ก์ ์๋ํ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ทจํด ์๊ฐ์ ์ ๋ํํ๋ ๊ฒ์ ์๋ฏธ