\n \ub370\uc774\ud130 \uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc758 \uc774\ud574\ub294 \uac1c\ubc1c\uc790\ub85c\uc11c\uc758 \uc131\uc7a5\uc5d0 \ud544\uc218\uc801\uc778 \uc694\uc18c\uc785\ub2c8\ub2e4. C++\ub294 \uace0\uc131\ub2a5\uc758 \ud504\ub85c\uadf8\ub798\ubc0d \uc5b8\uc5b4\ub85c, \ud2b9\ud788 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc640 \uac19\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub110\ub9ac \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 ‘\uad6c\uac04 \uacf1 \uad6c\ud558\uae30’\ub77c\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uba70, \uc774\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \ub2e4\uc591\ud55c \uc811\uadfc \ubc29\uc2dd\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uacfc \uba87 \uac1c\uc758 \uc9c8\uc758(query)\uc5d0 \ub300\ud574, \uc9c0\uc815\ub41c \uad6c\uac04\uc758 \uacf1\uc744 \ube60\ub974\uac8c \uacc4\uc0b0\ud558\ub294 \ubb38\uc81c\ub97c \uace0\ub824\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. <\/p>\n
\ubb38\uc81c:<\/strong> \uc785\ub825:<\/strong><\/p>\n \ucd9c\ub825:<\/strong> \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uba87 \uac00\uc9c0 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0dd\uac01\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \ub450 \ubc88\uc9f8 \ubc29\ubc95\uc740 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac<\/strong>\ub97c \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ud615\ud0dc\ub85c \uad6c\uc131\ub418\uba70, \uac01 \ub178\ub4dc\ub294 \ubc30\uc5f4\uc758 \ud2b9\uc815 \uad6c\uac04\uc5d0 \ub300\ud55c \uc815\ubcf4\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \uc544\ub798\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uc774\uc6a9\ud558\uc5ec \uad6c\uac04 \uacf1\uc744 \uacc4\uc0b0\ud558\ub294 C++ \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n \n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\ucd95 \uc2dc\uac04\uc740 O(N), \uac01 \uc9c8\uc758\uc5d0 \ub300\ud55c \uc751\ub2f5 \uc2dc\uac04\uc740 O(log N)\uc785\ub2c8\ub2e4. \n \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc8fc\uc5b4\uc9c0\ub294 \ubb38\uc81c\uc5d0 \ub300\ud574 \uc801\uc808\ud55c \uc790\ub8cc \uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc744 \uc120\ud0dd\ud558\ub294 \uac83\uc740 \ub9e4\uc6b0 \uc911\uc694\ud569\ub2c8\ub2e4. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n
\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 A<\/code>\uc640 \uc9c8\uc758\uc758 \uc218 Q<\/code>\uac00 \uc788\ub2e4.
\n A[i]<\/code>\ub294 \ubc30\uc5f4\uc758 i\ubc88\uc9f8 \uc6d0\uc18c\ub97c \uc758\ubbf8\ud558\uba70, 1 \u2264 i \u2264 N<\/code>\uc785\ub2c8\ub2e4. \uac01 \uc9c8\uc758\ub294 \ub450 \uc218 L<\/code>\uacfc R<\/code>\uc744 \ud3ec\ud568\ud558\uc5ec, L \u2264 R<\/code>\uc77c \ub54c A[L] \u00d7 A[L+1] \u00d7 ... \u00d7 A[R]<\/code>\uc758 \uac12\uc744 \uad6c\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n\n
N<\/code> (1 \u2264 N \u2264 105<\/sup>)<\/li>\nA[1...N]<\/code> (1 \u2264 A[i] \u2264 109<\/sup>)<\/li>\nQ<\/code> (1 \u2264 Q \u2264 105<\/sup>)<\/li>\nL<\/code>\uc640 R<\/code> (1 \u2264 L \u2264 R \u2264 N)<\/li>\n<\/ul>\n
\n
\uac01 \uc9c8\uc758\uc5d0 \ub300\ud55c \uad6c\uac04 \uacf1\uc744 \ud55c \uc904\uc529 \ucd9c\ub825\ud55c\ub2e4.\n <\/p>\n\ubb38\uc81c \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\n
\n \uccab \ubc88\uc9f8\ub85c, \ub2e8\uc21c\ud55c \ubc29\ubc95\uc740 \uac01 \uc9c8\uc758\ub97c \uc704\ud574 \uc8fc\uc5b4\uc9c4 \uad6c\uac04\uc758 \uacf1\uc744 \uc21c\ucc28\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.
\n \uadf8\ub7ec\ub098 \uc774 \ubc29\ubc95\uc740 \ucd5c\uc545\uc758 \uacbd\uc6b0 O(N * Q)\uc758 \uc2dc\uac04\uc774 \uac78\ub9ac\ubbc0\ub85c \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \uc801\uc740 \uc2dc\uac04 \uc548\uc5d0 \uad6c\uac04\uc5d0 \ub300\ud55c \ud569, \uacf1 \ub610\ub294 \ucd5c\ub300\/\ucd5c\uc18c \uac12\uc744 \uacc4\uc0b0\ud558\ub294 \ub370 \ud6a8\uacfc\uc801\uc785\ub2c8\ub2e4.
\n
\n \uc138 \uadf8 \uc601\uc5ed \ud2b8\ub9ac\uc758 \uac01 \ub178\ub4dc\ub294 \uadf8 \uc9c0\uc5ed\uc758 \uacf1\uc744 \uc800\uc7a5\ud558\uace0, \uc774\ub97c \ud1b5\ud574 \uad6c\uac04 \uacf1\uc744 O(log N) \uc2dc\uac04 \uc548\uc5d0 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\uc758 \uad6c\uc870<\/h3>\n
\n \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub294 \ub300\uac1c \ub2e4\uc74c \uac00\uc9c0 \uc8fc\uc694 \uc791\uc5c5\uc744 \uc218\ud589\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n\n
query()<\/code>\ud568\uc218<\/li>\nupdate()<\/code>\ud568\uc218<\/li>\n<\/ol>\n\ucd5c\uc885 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n#include <iostream>\n#include <vector>\nusing namespace std;\n\n\/\/ \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac \ud074\ub798\uc2a4 \uc815\uc758\nclass SegmentTree {\nprivate:\n vector\ucf54\ub4dc \uc124\uba85<\/h3>\n
\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
\n \ub530\ub77c\uc11c \uc804\uccb4 \uc54c\uace0\ub9ac\uc998\uc758 \ucd5c\uc545\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N + Q log N)\uc785\ub2c8\ub2e4.
\n \uc774\ub294 \ud070 \uc785\ub825 \ub370\uc774\ud130\ub3c4 \ud6a8\uc728\uc801\uc73c\ub85c \ucc98\ub9ac\ud560 \uc218 \uc788\ub3c4\ub85d \ud574\uc90d\ub2c8\ub2e4.\n <\/p>\n\ub9c8\ubb34\ub9ac<\/h2>\n
\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc138\uadf8\uba3c\ud2b8 \ud2b8\ub9ac\ub97c \uc774\uc6a9\ud55c \uad6c\uac04 \uacf1 \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ub2e4\ub904\ubcf4\uc558\uace0, \uc774\ub97c \ud1b5\ud574 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc774 \ubb34\uc5c7\uc778\uc9c0 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4.
\n \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud480\uba70 \ucf54\ub529 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uae30\ub97c \ubc14\ub77c\uba70, \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \uc8fc\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \uac00\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n