Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"POJ-2155\":[\"Matrix\",8926,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dPOJ+Monthly\\\"\\u003ePOJ Monthly\\u003c/a\\u003e,Lou Tiancheng\\u003c/div\\u003e\"],\"HDU-5306\":[\"Gorgeous Sequence\",2093,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2015+Multi-University+Training+Contest+2\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2015 Multi-University Training Contest 2 \\u003c/a\\u003e \\u003c/div\\u003e\"],\"Gym-103861L\":[\"Fenwick Tree\",377,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103861\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2021 ICPC Asia East Continent Final\\u003c/a\\u003e\"],\"洛谷-P3834\":[\"可持久化线段树 2\",39812,\"模板\"],\"Gym-104095J\":[\"二进制与、平方和\",265,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104095\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2020 CCPC Henan Provincial Collegiate Programming Contest\\u003c/a\\u003e\"],\"HDU-6992\":[\"Lawn of the Dead\",411,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A84%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021“MINIEYE杯”中国大学生算法设计超级联赛(4) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"Gym-103069G\":[\"Prof. Pang\\u0027s sequence\",264,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103069\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2020 ICPC Asia East Continent Final\\u003c/a\\u003e\"],\"洛谷-P3919\":[\"可持久化线段树 1(可持久化数组)\",21909,\"模板\"],\"CodeForces-786B\":[\"Legacy\",5892,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/786\\\"\\u003eCodeforces Round 406 (Div. 1)\\u003c/a\\u003e\"],\"HDU-6230\":[\"Palindrome\",698,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2017%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC-%B9%FE%B6%FB%B1%F5%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B9%FE%C0%ED%B9%A4%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2017中国大学生程序设计竞赛-哈尔滨站-重现赛(感谢哈理工) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"Gym-103627A\":[\"Points\",120,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103627\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eXXII Open Cup, Grand Prix of Daejeon\\u003c/a\\u003e\"],\"HDU-7185\":[\"Pandaemonium Asphodelos: The First Circle (Savage)\",88,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2022%A1%B0%BA%BC%B5%E7%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A85%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2022“杭电杯”中国大学生算法设计超级联赛(5) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"Gym-104008H\":[\"Hysteretic Racing\",13,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104008\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2022 China Collegiate Programming Contest (CCPC) Guilin Site\\u003c/a\\u003e\"],\"黑暗爆炸-3881\":[\"Divljak\",110,\"Coci2015 鸣谢 Dzy\"],\"Gym-104008I\":[\"Invincible Hotwheels\",6,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104008\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2022 China Collegiate Programming Contest (CCPC) Guilin Site\\u003c/a\\u003e\"],\"POJ-2464\":[\"Brownie Points II\",649,\"\\u003cdiv class\\u003d\\\"ptx\\\" lang\\u003d\\\"en-US\\\"\\u003e\\u003ca href\\u003d\\\"http://poj.org/searchproblem?field\\u003dsource\\u0026amp;key\\u003dWaterloo+local+2005.06.11\\\"\\u003eWaterloo local 2005.06.11\\u003c/a\\u003e\\u003c/div\\u003e\"],\"洛谷-P3369\":[\"普通平衡树\",112215,\"模板\"],\"Gym-104090M\":[\"Please Save Pigeland\",145,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104090\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2022 ICPC Asia Hangzhou Regional Programming Contest\\u003c/a\\u003e\"],\"洛谷-P3865\":[\"ST 表\",74646,\"模板\"],\"HDU-6967\":[\"I love data structure\",110,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A82%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021“MINIEYE杯”中国大学生算法设计超级联赛(2) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"HDU-6989\":[\"Didn\\u0027t I Say to Make My Abilities Average in the Next Life?!\",116,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A84%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021“MINIEYE杯”中国大学生算法设计超级联赛(4) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P3368\":[\"树状数组 2\",60861,\"模板\"],\"洛谷-P4556\":[\"雨天的尾巴 /【模板】线段树合并\",11937,\"Vani有约会\"],\"HDU-6609\":[\"Find the answer\",1064,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2019+Multi-University+Training+Contest+3\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2019 Multi-University Training Contest 3 \\u003c/a\\u003e \\u003c/div\\u003e\"],\"Gym-103470E\":[\"Paimon Segment Tree\",148,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103470\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)\\u003c/a\\u003e\"],\"QOJ-1856\":[\"Interval\",44,\"\\u003ca href\\u003d\\\"https://qoj.ac/contest/695\\\"\\u003ePetrozavodsk Summer 2021. Day 5. Shanghai ICPC Camp 2021 Onsite Day 2 by PKU\\u003c/a\\u003e\"],\"HDU-6888\":[\"Art Class\",86,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2020%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC%A3%A8CCPC%A3%A9+-+%CD%F8%C2%E7%D1%A1%B0%CE%C8%FC\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛 \\u003c/a\\u003e \\u003c/div\\u003e\"],\"HDU-6964\":[\"I love counting\",314,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A82%A3%A9\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021“MINIEYE杯”中国大学生算法设计超级联赛(2) \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P1908\":[\"逆序对\",101434,null],\"Gym-103535B\":[\"Fall with Soldiers\",3,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103535\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2021 HDU Multi-University Training Contest 7\\u003c/a\\u003e\"],\"Gym-104021G\":[\"Pot!!\",690,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104021\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2019 ICPC Asia Yinchuan Regional Contest\\u003c/a\\u003e\"],\"Gym-104053E\":[\"Elevator\",1051,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104053\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite\\u003c/a\\u003e\"],\"Gym-104120F\":[\"Fence Painting\",85,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104120\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2022 ICPC Gran Premio de Mexico Repechaje\\u003c/a\\u003e\"],\"洛谷-P3372\":[\"线段树 1\",157579,\"模板\"],\"洛谷-P3373\":[\"线段树 2\",65997,\"模板\"],\"洛谷-P3374\":[\"树状数组 1\",95497,\"模板\"],\"Gym-104053B\":[\"Ayano and sequences\",57,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104053\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite\\u003c/a\\u003e\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"George_Plover","updateTime":1683802606000,"title":"(Section 7) 树状数组、线段树","dislikeCnt":0,"content":"**一些博客链接这里面没有包含,请见[飞书文档](https://fudanicpc.feishu.cn/wiki/LfVAw7nUmiUVCOkjFl1cZvrDn0e)!**\n\n数据结构题一般由 思路+实现 两部分组成。\n思路通常来源于一些经典维护技巧,需要见多识广;实现能力则依赖于多写多练。\n如果一道题,一段时间内想不出初步思路,可以找题解学习思路并感悟。\n\neasy级别的题目一般为区域赛中 签到 到 铜牌 水平\nmedium级别的题目一般为区域赛中 银牌 到 金尾 水平\nhard级别的题目一般为区域赛中 金牌 到 捧杯 水平\n\n## 树状数组\n### 基础部分\n#### 模板\n[problem:洛谷-P3374] 树状数组模板 单点修改,区间查询\n[problem:洛谷-P3368] 树状数组模板 单点查询,区间修改\n#### 区间加区间求和\n[problem:洛谷-P3372] 虽然是线段树模板,但是可以推导后用两个树状数组做\n#### 二维树状数组\n[problem:POJ-2155] \n#### 二维偏序(逆序对)\n[problem:洛谷-P1908] 经典问题\n#### 树状数组维护不可差分信息\n[problem:洛谷-P3865] 用树状数组做,两个log的复杂度,可以维护区间最值\n\n\n\n\n### 综合题\n建议已经掌握模板的同学尝试\n\n[problem:Gym-103861L] easy 2022ECFinal\n[problem:Gym-104053E] easy 2022CCPC-GuangZhou\n[problem:POJ-2464] medium- 经典扫描线问题\n[problem:HDU-6609] medium-\n[problem:HDU-6230] medium\n[problem:HDU-6964] medium+ 经典套路,有综合性\n[problem:HDU-6989] hard\n[problem:QOJ-1856] hard+ (题解:https://www.luogu.com.cn/blog/George-Plover/post-2021-icpc-hua-wei-tiao-zhan-sai-prod-interval\n\n---\n## 线段树 \n### (I) 简介\u0026基础入门\n#### [1]静态区间查询\n[problem:洛谷-P3865] 静态区间查询,可用线段树做\n#### [2]区间修改区间查询\n[problem:洛谷-P3372] 懒标记维护模板\n[problem:洛谷-P3373] 加深对标记维护的理解,通过后才算入门\n\n---\n### (II) 进阶部分\n#### [1]矩阵tag\n[problem:Gym-103470E] 【ICPC-2021 南京】Paimon Segment Tree\n[problem:HDU-6967] \n[problem:Gym-103069G] 2021ECfinal\n#### [2]动态开点线段树\n[problem:洛谷-P3369] 普通平衡树模板,可以用动态开点线段树实现\n#### [3]可持久化线段树\n[problem:洛谷-P3919] P3919 【模板】可持久化线段树 1(可持久化数组) - 洛谷 | 计算机科学教育新生态\n[problem:洛谷-P3834] P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态\n#### [4]线段树合并\nOiwiki 线段树 中有提到\n[problem:洛谷-P4556] P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 - 洛谷 | 计算机科学教育新生态\n#### [5]线段树势能分析\n\n---\n### (III) 变体与运用\n#### [1]线段树优化建图\n[problem:CodeForces-786B]\n#### [2]线段树LogUpdate\n[problem:Gym-104008H] CCPC2022桂林\n#### [3]Segment Tree Beats\n[problem:HDU-5306] 模板 HDU5306 Gorgeous Sequence \n[problem:HDU-6888] 近年的一道网络预选赛题 题解:\n\n---\n\n### 综合题\n\n[problem:Gym-103627A] medium+ 妙妙题\n[problem:黑暗爆炸-3881] medium+ [COCI2015]Divljak 与字符串结合\n[problem:Gym-104008I] hard 与字符串结合\n[problem:Gym-104095J] medium 有题解\n[problem:Gym-104120F] hard- 妙妙题\n[problem:Gym-104090M] medium+ ICPC2022杭州\n[problem:Gym-104053B] hard- CCPC2022广州\n[problem:Gym-103535B] hard 思路比较hard,实现不太难 航电多校\n[problem:Gym-104021G] easy+\n[problem:HDU-6992] medium- 有没有可能不需要用线段树?\n[problem:HDU-7185] hard\n","threadId":143956,"likeCnt":0,"createTime":1683801700000,"isWorkbook":true,"viewCnt":1507,"openness":2,"fav":false,"id":3652,"trustable":false}