寒江陪烟火🔥

树状数组

acm相关(6) dp(68) RMQ(5) STL(6) 主席树(2) 二分匹配(23) 二分查找(2) 分治法(3) 划分树(1) 单调队列(2) 博弈(11) 字典树(3) 字符串处理(1) 学习(1) 并查集(4) 强联通分量(3) 归并排序(1) 拓扑排序(1) 搜索(1) 数论(8) 最小生成树(3) 最短路(5) 树链剖分(4) 欧拉回路(5) 简单模版(14) 简单题(24) 线段树(13) 网络流(6)

/ 注册

全部文章 / 树状数组（共7篇）

codeforces703D Mishka and Interesting sum（区间偶数异或）

题意：给你一个序列，q个询问l,r 要求出l到r区间内出现偶数次的数的异或值思路：预处理异或前缀sum 将询问按r放入vector，存的pair<l,i> 树状数组部分有点同于求区间数的种数。 last记录每个数前一次出现的位置。走到i时，如果a[i]出现过，那...

2016-09-20

0 224

HDU5775 Bubble Sort（树状数组求逆序数）

题意：给你一段序列（排列）和排序方式让你求出每个数在排序过程中移动的范围思路：序列排序结束是升序的，能移动到的最左端就是min(i,a[i]) 如果a[i]比较大，他就不会向左移，就是a[i]，如果比较小就最多移动到i的位置能移动到的最右端就是当前的i加上从右向左比他小的数的个...

2016-07-29

0 230

POJ2155 Matrix（二维树状数组）

题意：给出矩阵左上角和右下角坐标，矩阵里的元素 1变0 ，0 变1，然后给出询问，问某个点是多少。 #include <iostream> #include <algorithm> #include <cstring> #include <cmath...

2015-09-05

0 229

POJ2299 Ultra-QuickSort（树状数组求逆序数+离散化）

原文：http://blog.csdn.net/alongela/article/details/8142965 给定n个数，要求这些数构成的逆序对的个数。除了用归并排序来求逆序对个数，还可以使用树状数组来求解。树状数组求解的思路：开一个能大小为这些数的最大值的树状数组，并全部置0。从头到尾读...

2015-09-05

0 215

HDU1556 color the ball（区间修改，单点查询）

#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #i...

2015-09-05

0 237

树状数组模版

int lowbit(int x) { return x&(-x); } 修改某个位置上的值，查找一段区间的和（向上修改，向下统计） void update(int x,int num) { while(x<=MAXN) { c[x]+=nu...

2015-09-05

0 217

POJ2352 stars 修改某个位置上的值，查找一段区间的和（向上修改，向下统计）

链接： http://poj.org/problem?id=2352 题目大意：在坐标上有n个星星，如果某个星星坐标为(x, y), 它的左下位置为：(x0,y0)，x0<=x 且y0<=y。如果左下位置有a个星星，就表示这个星星属于level x 按照y递增，如果y相同则x...

2015-08-11

0 230