3212: Pku3468 A Simple Problem with Integers

时间:2023-03-10 05:01:36
3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1053  Solved: 468
[Submit][Status][Discuss]

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. 
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. 
Each of the next Q lines represents an operation. 
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. 
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

HINT

The sums may exceed the range of 32-bit integers.

Source

题解:其实就是个英文版的线段树模板题,连乘法覆盖啥的都没有,也就是说所有的修改操作压根就没有顺序之分,可以爱怎么瞎搞怎么瞎搞= =

PS:话说我的线段树居然全方位怒踩树状数组是什麽节奏啊啊啊QAQ(上面的是树状数组,下面的是线段树)

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAA+IAAABKCAYAAAA/ve5VAAAgAElEQVR4Xu1d27JsS1Fda+91DuItQkOeBAVEA14QCdGvESK88MJHGHyEL4iE6NcIEV54kVAEFH2SUMMLZ599ddfsU6urq6tqjKzKmnN29+iIFefsnlWZWSOzMnPMW9+/efu5c/i8fv36Lvy9fPly+e/Tp0/v3nnnnbsnT55Q0oMZ9/f3y9gXL14scsInzH/33XcfjwXZYdyrV6/uwpygQx8h4I2A4tkbUcnbEgHF85boS7c3Aopnb0Qlb0sEFM9boi/d3ggonm2I3teIeOTnkRwzYgOBDg4Ic8NfINCBkIfvWoQ8JeGRzAeiHT6BaD88PDDqr2pMen6k5IP8OBp/CeD0xBy7rh7ZimcWXTwOxafiGWOYjlA82/DyHq149kVU8eyLp1Wa4tmKWHu84tkXT6s0xbMVMcWzL2I2aY9EvCdx5KoCcYkEOhwLBDol0fnF95xgBhIe5ser3YG8h/mBzOvTj0A80VG7+SH3A0piLUuQj/tXYZupeLbhdUmjFc993lJ+7sNt9izFcx/Ciuc+3GbPUjz3Iax47sNt9izFcx/Cimcet7Mr4r/8e3/Fz9bIMwT+7S9/d/lOOO4vOOSbsk+Ey/5iVRZhBBS3GKOtRsg3PsgLRx8ccynCdQ6ua0qVD9dEW7q8EYjxG+SeEPFw5uejX/yWt76bkqfksF93/+tf/M7yfgGdJDn1kWJ2vzEry+oIKG73Gx3yjY9vhKMPjrmUH33zC0svoH53Dr5rSNXeWANl6ZiFQJGIx5esfeIP/maW3puQq+SwXzf/y5//9vKuAhVfEfH9RqksYxFQrmWRWn+cfOODuXD0wTGXopPyc3BdU6r2xppoS5c3AkUi/v777y8vVfvUl7/jre+m5Ck57Nfd3//65xYi/vHf/+v9GrmBZYrZDUCXymEEFLfDEE4TIN/4QCscfXDMpQjXObiuKVU+XBNt6fJGgCLi6aCSAbNv7803Wcue2bZYHFCzu2ajkokF3bGx3/vaZxcB8WTTmjHF+pkdN4bE6WzLXgszt95vJYzCd1vb5ekTycIItOK2FAvpflesYHxHRqS+Qb1E1BN8skX+G1nn7LnWfmK2PdciP+AaLjx97EvfPltSKV6988WsOJ8l18vveZ0esbc219N/I/YxmHn0MsqvDNL7G1Mk4s+ePVt+cowhKWnhnLU8KznYA0EINlgL5+yNPss/lyj3n/70N00x7ll8WT+z4zzxv7S9Zt1jnlhJ1n4QEBHfjy9yS0TEfXyjXOeDYy4l3JoeHsdM745DhGaLfsC6+i36B9bGGuns7d1b8ko29fhvNp4e+xvFrU50shG67rgiEX/+/Pnys2E5Ed/qyoIlQGdvFot7LHaXiLtFl8baEAgvaAk/qfDJP/zbZSJzRrUneZesYmOUHWdbeXu0JWbT5OGFjXUtFnutsjX+chBAJ5DS+Mybla1i93LQHbO0lce2yHFjq9lutnLdHOwDruFxzNgL7LUfsK5+z3trNhGf0c+tjaeHPg8Z1rjTeDsCRSIef/Pt1/7o75okJapjC0RrXKs5YuXX7LHD4jPDw+7SGS7rCZHUDm3Mg28DDuntaJZmEeGJGv3S/GBT7teeYoJkI/LsEbNpI1NaV3487rYSWUKY1NZbkumzqyVljwh4EvHWHvHaX7X4bMVzK+/v+WSCJbemscX2C3HtbG6r5aQ9xjWLB7Id9RG9cRexZOtGKRaQbXlfV9NZG8dgkxJx1COF46gHa8VYHqc9dR6tKa2xbG7oyXtMfc8fM6n52xqDvXujN1ZR7s/jL113ilMN5xm9jCX3ovVde35l9tSsMSm2jz9fFq6IB5LCEPGSc1BiKRXO0gLzcbV/53NRIp0FJrID2YWayVR+6wpPnhzZQrcWLnvQY03GtUSaN9QlrBl/lBrznqalpr+GuYXo1uKbWR+K1xqOFvsU53vYWdvY0NrPeeMc/732/vLMDaWmbxvksVZLM8g011jjYQTKOSxBYfXNHsfWrFaezo9Ze7Ewv1VjUI/m2eO0amatVyr5KNhkIeI1GaXva/ULjfWoZajfLO21Gm6or0B7LfVVbW0WHbUYr8Vza6978BV2/S2/74WIs3kMrfnS8iu77hnjikQ8f2s62iC1osc20Wi+tQBZEtAMUGtNErKLWefImBznmWvfu+yAY+mKeM3uWtJB36d7p3XlpjWu1dy0GhtGn2WPWrAp4dKzDtY+1ADuPR5l3xgCiIjH3FdqdnriMs2llr3LzkM1MSVEe294ZhBxS25rnXDZO3YlsmTNdcz6SzFcijFrPbPmb2+dqOeK+kaIuBUTNge0aiiTLZm11/II01fM8hWT+xART23Lx6KYRP076z92XG0/s/5rxYIl91rj2FI3mXi95TFFIl67Il4CqlTIrGeY0MZgyGerYG3l4FG78xMgLaxbvvHY0FthOEtv/oKW1skmFJ+1xI0SOpLbKoa14sI0Xa0mvkdnae8x8RjHeOYQxfqsHbNvuZ5EnIld1CSzub93XGsP781TlmawVcd7c5slt+8NOyseyP5aTzG7Z0M1skSc0AmH0VqV2uRBxK31HPUHbL9d8zlbC5n9sUZ8sDpK62VyTDoP5e9SfmXtG81TKO7RHme5EFN7mLUw8WOx+RbHmog4uvqHki3jeGYDoASDjq/laHa9LdxKQV7zg4WcrYXBXvX88BufX15IyDx+ka+BTcio0FoLN5PwmMTZauKZmE3tqK0BNRFsXPdidElXuva6Ry7Jrmsn4vme3UuNY2KEaZKZk3G9uY3Jm8w6th7D5GZEyqw9Aquzd1yJgEcbESEREW9HJJsjmP3B9jwj49i5ViJeIqbhu974svYktX4L7RnWf60osOTeW8+vW+b3IhGv3ZrearrXPMOEAhQdXwtwtNFYglcqViiJlJKPyMkRlfDzZeFziUS85cfeZNp70iAtaC2CzzaIKK7RntrL3l8rx0jPAQE2LloNGBM7vfuLbTLZxomxdS+xwa4J1UNv7PeCD2sHinEmx1pvg2V1jo7r2ZesToRvkGO5Ih7Gr9nvIvuR31Hfx+SS0fzF+IrVUVovI7+3xxntSWp9EbKZ8QuKDUvuvfX8irCcebxIxMNb08Pzs+inndgAS8e1Ei67USzBNRM8JLu20XLyYsGHkYk2OLL7Fo5/72ufvXt4eHj87VBL0kMFoxTjI9/lhcDatLAJliE0aWy05I7a6Cn7FuL51teIcl5a6BAZGY3d1j5i8wD7GBJqsvcQF731GvmU7T8Y3+8BJ2QDgwdDUix53tJvoN6O9cOoTmRHjlFOxGtxhfo0dm+PjLPsd7anYfyCeh6mR0F+YXUwMV5aE/IfuuO3hVPP2tB+Zv3XyhuW3Mv2iZb9aYlXlP+u+XiRiLNXxFFg14AbPcOUGo10bOk8RCZKtllvO899EGUyZ2y3xGZr3eEZ8fv7e3h7EpP00zG12BzxK5qLfM0mWEuDVtv7lnhsxT/a4wyZSovj1vEm/XMRYJsatmFKrfXaX5bcUGtgag3mXHTHpFuawVIubfULbG4rYX9pTWKrAe7NpdZerJbf877Dmr/X6oVq9bz2O+Jsf8nsbRY7poYyO5L1AaPPQpJbekuEPeZki458/dZeG/VUpfzPrKvUQ7Hfof3dk68sudeaSxGGPfYycX2NY86I+Js3b5bbdMKHvW0XnSmqbTR246EArTVNWzsMrS+3b+QqSKtBa23GrTHaSj9q3Ft2ITzzhJ37NZ3f4zfrHDbBlgqGZa3ojHKpyW7t3RKOjN9a+GwVb9I7FwE2LhCpzpvS1t6NK+rZX3EuI7+2by6l0bE0g6W1ehBx5Ne50ekj3dIHxZ4rj9E07kp1iI3HPMcyRCjI9hpXk9Xj52DTs2fPHvtda51qYVzyPINdzzpyXS3imMcH0od62Vrc1Hr/kj6rjlauqPmktO7clprNI30bUyPQ3ujJ95bcy9hY6hFLWPfY6pMlL1NKuleX3xEvEfHLXNr2ViMSs72Ft2uBfFP2vXC53T1xySu/lbi9xHUGm0Nf8dEvfuuSQ2xz2/fg+xGy1AvgbJ1Bfn5FvNfWW58321c1fPewN27d91p/PwJnRDy8STo8Ix4+8Yp4v/jbnqnksF//yzci4vuNTllmReDa93N+deuSrjiIiFujeb+52XqV1WPls3VeGhFHeATMt8oPyLZZdl17/g8+Rdhu6XePfX7LMk6I+NsXtL0JRPzly5ci4g5RcQvJwQGmTUTIN/tt9jYJCCm9aASufT+nhXpWMzsrAETEfZDdS4zXCMHMuJyp80ff/MJy8Sm+nNjHW/Ok7J2QzfRVDdW97I15XhcRn4nt1rLPiHh8Y3q4lexTX/7O1vZdtP5bSA6X6iD5RkT8UmNXdp8joP2836gQEffxjWLcB8dcyg+/8fmTXwmao0VSZyKgvTETXcmejcAJEX97NfxNIOKBhIuIj0Ov5DCO4SwJ8o2I+KzYktz1EdB+Xh9zVqN8wyLVHiccfXDMpXz/65+7e/LkyeNPmc7RIqkzEdDemImuZM9G4IyIP3/+fNEpIj4OvZLDOIazJMg3IuKzYkty10dA+3l9zFmN8g2LlIi4D1I2KT/4s9+6e3h4uPvYl75tm6jRu0FAOWY3rpAhHQicEPG3JHx5a3r4feVwhjD+N5Ubj3fo0hQhsAoC8Y6O8L4DxfMqkEvJRAQUzxPBlejVEVA8rw65FE5EQPE8EVyJXh0BxfPqkJ8ovA8vawtOiJ9AxMOfiPi2jpH2PgRiQlE89+GnWftCQPG8L3/ImjEEFM9j+Gn2vhBQPO/LH7JmDAHF8xh+vbOX3xHvnax5QkAICAEhIASEgBAQAkJACAgBISAEhIANgeWKeJiSXwW3idFoISAEhIAQEAJCQAgIASEgBISAEBACQoBB4PHW9PB8uD5CQAgIASEgBISAEBACQkAICAEhIASEwFwEHm9Nj3eo68r4XMAlXQgIASEgBITANSOgF7xes3e1NiEgBISAEPBCwP0Z8ZTI54+ft0g+Glt6lL30UrkcmJY9pbF7fWQ+vD+v9TQ/Ou4VMFFO9j6/M/G38uaBFIfamnOsev1okePt72uSd//V+7s3f3w7r8a4tfV6xmqoH0ztiTpbdcxLTtDVrFOoGKDjngA6yPKq85ZewMHsaSJatXevdbcUcnFvoV7iEO9tOFP5FxbexZcj9/SxKL5r/Xctl6CLcnvtla0bzyu/HHvjsZpRst/btzUdTCxY/V6rocEGtK6WL1tykS96MB61t7kWz5e15cD0AsXI8RqTOgw2ONYd7jgeFRd03NGURVRL39q2eK+NlZevs9xsnDYRCLda08HoYu2+5XGRlO6dnHra5ynrlmInNgk1Ao0akp4axTRIsK6iBIyO78jJPRiW8GHk7GjZTVNQDUGkdYt1IiI+avMlYhIb+/xXi0on82aMQXGACBTKf0j+Ho4zeYEZw/AImLcrgDD6e2X32G3RZamhXnKZNeVQ92BssRfFutsV8ZpRyFgGgDxhMbqYManD4q10e00uqHdCx1EgWI8jfei4Vd/exo+Q7tZcRu4xbvGVgr3htrU9IuJbe+Ay9Mf6Yakj6crYedb6mNesIpoo+aLjO3ERg6HXmJ0smTIDuQ8dp5Q4Dzo/kXy8auhh7yUS8d7Y7emZS6Qfubg3NyG5eznei38Ny9GaUcKFsbHHt6VaxZzAtOhq4cGuq4UJc6IIxTDyJaq3jHwm3jcl4pZFMGPTMayjmTkMkLPHoGJVI3CpXelZ5zg+/Dd+8rPS6bEwpjS/tu7UHpZc5ragNc/G3Cqftbd1dZuVcUggIuJmH331cFs6ukocjj/ui8Jt7CPH05MBJR2p7GXfJfqR3iUuMtvRWq0YXvt4VBOstajU9FgamlYzUvRFLTGkST8k81by37GTkX9y09le4GReq0D2Fk0nTFHet/YCsZbUeoX4PQoXS79w6kN7HWv1Cnnvgdbl5BY3MSi/9BBxJNOcY5b+o3wLthsQGwli8kvLByyhZZbH5K4RPzBrZfOppc4xNiMce7Hp0c3oYvxZG3O1RLzU6CAHoOMjQI/OtRZfRH5jIauRa2Z+65loRNpbZDRtDEZvWRvFnZ1fwrO66RoEGvn5NNnZGxh2Pdc4LiekNYKKxnkcD/jmBLv172VPfHAS4bExzv5dG5PrukbfzlpTrRnI9TG3r5eaN0aOuUlmkvcSFMmDt5bEMwtsUm6peQzfxU+PL85U1wpkCzeEO7k+NAy5CtXWWF+j+xmzkUwk43x+/xXxki2pW5CtCN+tj7f60Bjn6Fb1g49TjJMrLh8sEN39iexA87fGsVc/Q06t2KT5qZWncpsZAtgrm9WVjivFH8K5RahR3m7JZvgaM6aEwyGfnL6YonXyBWGAjm9GxC0AMWNbAcsGPqMHATrreH62uaSnVVitxZcp9rW1lq6st76r6UI2zMLaIhddJTjf5D4v3bsEbCw4rjG2h8ie+a9Afk8KVeV4qps5AcDYuuzpRB8jdw2cr0kHOisf19pTf1jZ5oYJMZELTri1kxksMWF7geLtRla2OWkjtHI/cv0xXo91CNWS3uPpPETEW1Ax54vaui7nhLVXHjn0e6dEHBGLGiEp95rX+bJTlmz1EHEr/rkPT/qMQd+WfIrWROfOTHjrZDaTt2u5geFrzJi0hqM1jpw4aOU4NyJeCprW2RMrQOjsG9PUIJ3o+KS6SontLYYHvxxVsGfBR/Wh4tkqnKVmgQJp40EIs+iL3remnybiy2kuNnbLo3qG3KLbuHuPWwkzY+sSTyLiU8PLUhNQE8fKQuPQ8RMSicjjhSUVhHHaVLWaPBOGrYLEFDLnCG2dlEd3kLG9wEhYIB3nPuRrGXMOiT0Z4ewWF3EwLpd+7vSW8BZ57+mba3voNCau/7b0Eqfxxgb5e5ZvS8GKbGHWzsodWZfFDnZNud0efNKSEFyJeAzcaEDrBWgsQMw4BjTGeYwuC7ieYxHJKxWfox8O/4d6hpaMMB+R61rxRr0gU1w9sZwpy3K1opy0cFOCYmHm+i5Vdv7cdboOdEv4SVwnxLfov7fHa5+oh7lyXSLiHnIv1X9b2W2pCenYkUajpZOyJyaIyIiYW5TyArEV4A29vXW+yxeoaB0bivPCeJJc/K8cWvM/IsbR9TWzGX1Ix2nvkRNJXPNqcJe+v1QiTu3tDxa8h1xjsXeH6eTMpN78kguy4ILGduWuQoww+CNbTvt7/kSMF649OFvW1JI/4gcKe8+fLysTi/pv6o2crTsmYJv84SaHQXXCGFQMEcnO+yy2zzjdfH23syFdt0DEkf9Qo8EenxB6VyGSIb/LHiGIdus3yNH8lo7W1W0vuVfhzBUXYSnks5tj2pacgLPMhE1SK+LvUee7mihUtNiEPAFTi8je2sr0EwiCmozcH97rYcN9gzCuqqT3toj4FLdZc4QXj4hywn/TT+RGVrtKZLkmu4fYonzMcsCRdVlssO6rEn4H7mTjmdYgdbsibjGUAWd0jMUei2OtAHuNR8WKKZxojIeOUnFGPU1vs+CFbY8ci80I19PNX786YJHTs6ZrnrM1EbfeQq5b0/cRjb1n85n6w4zpqk2IiViS1w7c0NP0Dp8UQUULsVD2eAe+ljrQ62rUKzA1S0Scc+4a8W3JNWzOYXp0DoFtR43izxDaHvxZAtgre6bdNUKLYssSU8zYkTHDNcQQ1m5EvBQ0vQEyAl4rAJBcdNyAq/tQVHxR4UQXSQ7+a1/xRsdrvUepLwxjW7e65/a6AzoosGQf27u1VPc2ToPLuerp6GoyIr0zji/xn/0sGbpFHtmx7OGvHn6e7XEvvv13ruuqne28OLaGMYTdawxcIkpEbPKCiuYPYGpyPqYX55PVIAxLxY6dMwgb6gVOe6DzE7vWXiDvDdheIa3x0eayb/hb02u2lHTV+pFB+F2no/gOxw9rS3L62+/Qi7889kAPQXUFZwVhCP9DvHHP5B/jjbt6yuhm9VttLEFbixkm/lquGqmhPXJP8x++hd5zj/WGrCsRj0ETjandeo42eG0x6e0aaEy6KZA9aAP1gus5DxXfGtk9rt1GtGPBS9eQE+e6D86PxOJ/2NTl38Bmxnhi6iErt/k0CdQ1sD/9VvJDzSce67lGGVYivmD+AYFd4nXl3xFv6Ud2leai9V+jz73WxNaqVq1D9Sc2AofceP6TKWytexyHzuYdWdFRNHrLlxegBjkpLvm0Fk4jvmhiyBDttCDEYmdYMzMU9QK5jJJJTL/QklN67UBel0on7mtEHK27pS/vJ1pr21OYbxHfrVxz7u/G+072BCQKnspxb/yjmtGaUTKX8RszpgXVDLuXfqRw4ijFqlYf0YkKdLymu3ViYKRWd4bhMs2diI8Yo7lCIEXA2nAIPSFwCQiIGF+Cl2SjEBACQkAICAEhIATmIiAiPhdfSScQYC40EGI0RAhcBAIi4hfhJhkpBISAEBACQkAICIGpCIiIT4VXwlkEVrijjzVF44TAVARExKfCK+FCQAgIASEgBISAELgIBETEL8JNMlIICAEhIASEgBAQAkJACAgBISAErgUBEfFr8aTWIQSEgBAQAkJACAgBISAEhIAQEAIXgYCI+EW46dzI8GbY0lsfw/evX79e/uL/h9lh7NOnT++ePHlyMi+MCX/Pnz9fjoV5Yey77767/PvFixfLd+GTvrU+yAp/6av/o6xXr1496o/64tjw7/ipreFCXSKzBxBQPA+Ap6m7Q0DxvDuXyKABBBTPA+Bp6u4QUDzvziU3bZCI+IW4P08cpZ9yi8Q7EOHwFz6B+KZ/+W/mxX+/9957C7GO8wIRD/8OJDzKi0Q7zEn/op54AiAS96D34eHhUf+FQC0zV0BA8bwCyFKxGgKK59WglqIVEFA8rwCyVKyGgOJ5NailqAOBMyL+3R93SNGURwQ+/UuH/xWO+wsK+absE+Gyv1iVRRgBxS3GaKsR8o0P8sLRB8dcinCdg+uaUuXDNdGWLm8EYvwGuSLizugqOTgD6ihOvhERdwwnidoYAe3njR3QUC/f+PhGOPrgKCI+B8ctpWpvbIm+dI8iICI+iqAakIkIzhOtxC0iPi+6JHltBLSf10ac1yff8Fi1RgpHHxxFxOfguKVU7Y0t0ZfuUQRExEcRFBGfiOA80UrcIuLzokuS10ZA+3ltxHl98g2PlYi4D1YWKYpPC1r7HCsf7tMvsopDYCoR/8xH7h+t+Pt/f3NiUXosNxWNzY+H+bm80phUTxiP5CAZCOJZyeEzH7l7a3tdOzqO7LYeD/pan5atVl1e42f4JsWhtuYcq14/WuRYMJuBi0X/2mM/8ydv88BXTnPT2jasqe9a17tG3DI1I/Vlq46h2sPKCeNaderTb+vcd7Pam8pGxz1ic7ZvWn1Gyf6aHz3WOlNGCcdW7d1j3T30auf9S/QJ6iUO8d5GOZXP9EKz49MSE5Y+thXHjBzLvmn16ygHWdbfO9bLhzNwG8n1tfwVv/eWHeWysWXlSKM1NMWjFpPWuptjzMhlxlhieRoRzwFnil9pDCOHGVNyYMlh6XeMzS2wvZLDeaDsj4i3iCcqnJaA9Rrr7Zu84JebjVO/tZqE2JCUsGN09eLkjUuvHWvMi6R07+TU0z5PWWv4iNUxO25j4a01PqghYWoUU28YORaifelE3IpHy49srG01rkbEL632IiI+2i+guprLn5072HixxLIlH/X21XnPXMtxTN5iMegd5+FDBn9mTEpmaycpejFj9PfK7rHbossSs0wcMLoZvEpE3FrPGXsZrhjGuL2srXXWo7VAFrR0nFVXHN+jywq2R3Io6URnedFx6zrQeKQPHUfyZxz39M0I6W7NZeQekye+UsDg6IkLo2/LMSLiW6Lvq3tm3NZqRtq4WOpabR5qLKy1LuhBRBsd9/DSLN9Y8UB+9FjrTBlWIh5s2WPtPT+RfLw70cPeSyTillhuxTEjhxljJScod83cF0ueG/yFIgYTZkye2y1zEEasrBFfWGOL1YVyLysnxQjNYfGyxvohr5bvqEY+rB2fckW8BwDLwpixpTEtAt9jMwJ9NDnU5KNiVSNwqbz0rHAc37q1unUrtMUellzmtiAdyBf58Vm+sRLj1tVty5otY1tYzcbF6qeZ41kiHsbFT+k29pHjqQ0lHanscDzVj/QuBSOzXVfEbRGFTvr21qK8mDNy6vWg3hTUiHb8Pv1vlN+6ld2G3mH0rJxiqdnIj+m6WpiEYzWc0mNhzBo4orxv7QUOcXnq5dpdWY/5qnCruKVfOPWN/YRyq1dI11+zaVZ89uyVfE4e45Y4TmUx81o5COUndNwDiy36lh7c0JxerJh81yu7tx4x+jzwaO2DnroY58ySa413EfEEsR6nbJMcbLemI/IbC1SJnMfCnBfjvMCxt8chW0r6SvZZAz0fP7P4Wuy1nr2vJx17A1OSNROXUZ95zs8JaY2gonEex8O6coLd+veyR7Jn20v2l8bkujwx3VLWGnFbO7mbr5u5fb1Uaxg5JYxbzVCJiKffRfKYkkbvq+QzfcPWbNQMprjWMAljajghnD32hscVcVR/0fFafa71DseG91ifPK+Il05kLznug5MDrRPd0baZ8Tnq9xFynOpm4r9XF0PGRnFA82f5cAZuQWZPrmeJeI/sfA7j07gOdBt3LQ6PucGOB4NhXEM6FtnKyvXA+KTmfHBHR/hus1vTGaenTmPA7H3+2+K07ZID0lwvRExhzIstc9a9ZlGLwLO2lIo/RqA9Ykbibt1RULKGwZV5Xg7JsWA1AxeL/rXG9hDZs2IFXvTGkPueMT1zHvfalb6cbo24rRFxVGtKDQczh6mLaExOENG/H8kJeMmbZZ/O9g2q2SxZb60dEW3vkxclfK1EnCGhPbW+5wWjrRP3p2SnHVmI8KP1lGrl7Pi07BVEWizHaz0zQ+jOal2BPMYxqB/vXb9l3gwfsnnDegKDrSMlH6CTvL2yWV2H/a/rCCwAAAfkSURBVFV/CTfyGWsfqmuMnNKJAi+5TP1GWKTHp1wRj87KX3wWvkeBhIxHQNZ0M8CxGw/Z+FjQB59bqelBxAtdZT0m0MP/obPgo/pQ8WSuriMbWJ/M9s2x+OEr1GhN6LhFF4vPjILG6l5znIj4mmjP17VG3DK157gnT28X760tSCc6nl/9zm+XRreue3hupm8QrkzDlq8Rke7HGpKcrNiSiNd8hE7ilk4co5qDjue2IB3n/sN1E9W9Nuk/lz8zPkf2D9rb6Dibi2rjUtutZHNk3T1zgw9fv3599w//8aRnenEOyi2juJ3vlfZzxz0nUBgbS4vvjS0EPiv3wEvsz2GfntSr/zKW9eQRYwszpobPNCIegYyKw8JHAol1TO/mGbWtBPCsBI+KYe12rWBj6ZYtRMQP2J+uEJHr0yTevkJ/jUQ8Ysbesl9OhrgpQbGAEmN+fFbMWu2YOT5/7jrVhW4JP4lr4op4bR1RT8/VbcZ+Ru5MjNeWvUbcWgqtV0Mw2gDnzztfExFHNRsdrzZFhbsBGHK+x2fEz5v94zet27dPcmLyDDhTbzD5TvuB/IQVrnlHclEeew1EnMk1vWN69gXShY7Prge/8YuvFyL+vf96cFFlOYE3mqOP8Xx5RJzlZewaT3mDiPiCx3d/7BLTj0J6EoDFgbXN01pFPDMyYlu1oO/ginitcCLyiwoumi8iXn9jLcIWNRrs8Z7duwah6bHLcw5LUtGLzUaPL0WsQubT75mr92cNNyHXE9OtZa0Rt5ZmczYRZ23Jn3e+plvTUc0Ox5nan49hSHeYg66Co+PWPWO9Nf0sJxR+v/vQSPPvnLGMZXqA8wsnIuLs3kbj0P44j4868enVZY3x3vG//guv7l69enX3/f9+t1dEN0/xJuJ53vLgKNHGmmxLLOxxbIknWuO/FTgo/g951H7iIOqcckXcAgBjvNeY08LQvnWw5FjrDp/VHFqKoYh42WuevmEwPsbTeKPBNE/WWM0TgvdJuF57ZsxjyO+CMXHFu/QW9UdfE2SYsYUl4i3yjmyagfOaMj33c83u3qskTD1kxvTUJES8L/nWdAtmrdqf+1tE/BSR3pPup5jX7sbTFXFLbLJje8hhz5yenDSjLnzi596/e/Pmzd0P//enhsT3YGCd4523vE76otjqtXuGXMYWZkweLMwcZow1CKcQ8QNR8CG6M0h4yT6LzSzIs5rDUSIebx2r3ZqWEz1063rLntJt8vlt7UFf61b33F4W/9Y4T9+U7EOYMWuwEHxGHjPGExdG39pjrOQakWCP40v8f+XNIxRI5rI/9db0k9BZI27ZAswQdq8xaP8gUnkrb01HzWB6HGEWx/Y+f498Vjs+44q4tRfIewO2V0hrfKxr5T3An6iu2VLSFTEt1dQ1cgfjc6bXZeKYkcP250fc+q+WM2sfHfPxn312d39/f/eD//lQt6g1cbPiX/NDbx1BINXkHvZW0qsYrwKP1NDcZgZDZsxacluYxxwUTia5vTU9DZr4/7WH49HZpJrx6e0aaEzpeCsgkM0oiB8L9Q5uTY/FKrU5kF50lrv1nHla6Eryc13ngX78JrclLZhHP+Db51ifzPRN6dm40npyWy3PkefP6iOs94CL1YaZ461EfInvDX9HvKUf2VWai9Y/E/uZstdoptla1ap1qLYEHbUx6bHzHHJsjtJj6Ip3/gx5mLvG7197xkILs5Ie1HD3EPGg59KeEY913FLra/U5xTmvUbV+o0bEUWyUfoml1iu01hblrJE70Jp69naLLJX0lV5YjPLR0d/1xzysL75CWPQcHyXiFvwt+Wa0ZtTyF/KbxUZrjhyR3YvHCF9DNbX2AvHZGJ/U6bdcMZDw8HiFOxHv2VDXNGcPCf5a8ER3AVjXKd+UERMu1kgaG3+txHgMFftsxa0ds7VmyDc+SAtHHxxzKcJ1Dq5rSv3Vn3nv7unTpy7PiK9pt3QJgYBAyEGBiL948UJE3DsklODtiHrc0s1olW9ExJk4mT1GRNwHYe1nHxxnSJFvfFAVjj44iojPwXFLqaNXxLe0XbqFQMzt77//voi4dziENzmGzz/+51Nv0Vctr3Rrm/eC1dSIiHvHVI88EfEe1M7naD/74DhDinzjg6pw9MFRRHwOjltKDS9rC5+RZ8S3tF+6bxuBmNufPXv7roO3l8ZPHjS75jcnr+H2kBzCCyQ8flJhDXtvSYeaGhHxW4r3a1+r9vN+PSzf+PhGOPrgKCI+B8ctpXq9NX3LNUj37SIgIj7R97/y0z9ZiPg//9+HJ2qR6B4E1NSIiPfEjebsEwHt5336JVgl3/j4Rjj64CgiPgfHLaV+8uef371+/Xr458u2XIN03y4CMbe/995751fEbxeWsZX/5Cc/WV4cEW4wCMkh/P8777xz9+TJk+W7QM7DJz6cH8aE78Jf+O5DHzr/CYZ0Xpwb5r18+XLREeY+PDwsuqL8sVVothA4IKB4ViRcEwKK52vyptaieFYMXBMCiudr8qbWYo3ns1vTBWEfAs+fH87OpZ9AksNfJNGRLIe35IVX1odP/C6Q6UDaIznPrQiyw1+YF0l4mBPn9VmtWUKgjIDiWZFxTQgonq/Jm1qL4lkxcE0IKJ6vyZtaizWeRcSdY2Z58P7tlerSFW5nVRInBISAEBACQkAICAEhIARuCoFwS2/4fPjDegz0phx/ZYsNF1f/H3A/OiqqoMfPAAAAAElFTkSuQmCC" alt="" />

树状数组:

 /**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
b,c:array[..] of int64;
i,j,k,l,m,n:longint;a1:int64;ch:char;
procedure addb(x:longint;y:int64);
begin
while x> do
begin
inc(b[x],y);
dec(x,x and (-x));
end;
end;
procedure addc(x:longint;y:int64);
var z:int64;
begin
z:=x;if x= then exit;
while x<=n do
begin
inc(c[x],z*y);
inc(x,x and (-x));
end;
end;
function sumb(x:longint):int64;
begin
sumb:=;if x= then exit;
while x<=n do
begin
inc(sumb,b[x]);
inc(x,x and (-x));
end;
end;
function sumc(x:longint):int64;
begin
sumc:=;
while x> do
begin
inc(sumc,c[x]);
dec(x,x and (-x));
end;
end;
function summ(x:longint):int64;
begin
exit(sumb(x)*int64(x)+sumc(x-));
end;
procedure add(x,y:longint;z:int64);
begin
addb(y,z);addc(y,z);
addb(x-,-z);addc(x-,-z);
end;
function sum(x,y:longint):int64;
begin
exit(summ(y)-summ(x-));
end;
begin
readln(n,m);
fillchar(b,sizeof(b),);
fillchar(c,sizeof(c),);
for i:= to n do
begin
read(a1);
add(i,i,a1);
end;readln;
for i:= to m do
begin
read(ch);
case upcase(ch) of
'Q':begin
readln(j,k);
writeln(sum(j,k));
end;
'C':begin
readln(j,k,a1);
add(j,k,a1);
end;
end;
end;
end.

线段树:

 /**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ var
i,j,k,l,m,n:longint;a1:int64;ch:char;
a,b:array[..] of int64;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
procedure built(z,x,y:longint);
begin
if x=y then
read(a[z])
else begin
built(z*,x,(x+y) div );
built(z*+,(x+y) div +,y);
a[z]:=a[z*]+a[z*+];
end;
b[z]:=;
end;
procedure add(z,x,y,l,r:longint;t:int64);
begin
if l>r then exit;
if (x=l) and (y=r) then
begin
inc(b[z],t);
exit;
end;
inc(a[z],t*int64(r-l+));
add(z*,x,(x+y) div ,l,min(r,(x+y) div ),t);
add(z*+,(x+y) div +,y,max((x+y) div +,l),r,t);
end;
function sum(z,x,y,l,r:longint;t:int64):int64;
var a1,a2:int64;
begin
if l>r then exit();
inc(t,b[z]);
if (x=l) and (y=r) then exit(a[z]+t*int64(y-x+));
a1:=sum(z*,x,(x+y) div ,l,min(r,(x+y) div ),t);
a2:=sum(z*+,(x+y) div +,y,max((x+y) div +,l),r,t);
exit(a1+a2);
end;
begin
readln(n,m);built(,,n);readln;
for i:= to m do
begin
read(ch);
case upcase(ch) of
'Q':begin
readln(j,k);
writeln(sum(,,n,j,k,));
end;
'C':begin
readln(j,k,a1);
add(,,n,j,k,a1);
end;
end;
end;
end.