KTH Matrix LineContainer Treap FenwickTree FenwickTree2d 4
SubMatrix.h
Description: Calculate submatrix sums quickly, given upper-left and
lower-right corners (half-open).
Usage: SubMatrix<int> m(matrix);
m.sum(0, 0, 2, 2); // top left 4 elements
Time: O
N
2
+ Q
13 lines
template <class T>
struct SubMatrix {
vector<vector<T>> p;
SubMatrix(vector<vector<T>>& v) {
int R = sz(v), C = sz(v[0]);
p.assign(R+1, vector<T>(C+1));
rep(r,0,R) rep(c,0,C)
p[r+1][c+1] = v[r][c] + p[r][c+1] + p[r+1][c] - p[r][c];
}
T sum(int u, int l, int d, int r) {
return p[d][r] - p[d][l] - p[u][r] + p[u][l];
}
};
Matrix.h
Description: Basic operations on square matrices.
Usage: Matrix<int, 3> A;
A.d = {{{{1,2,3}}, {{4,5,6}}, {{7,8,9}}}};
vector<int> vec = {1,2,3};
vec = (AˆN)
*
vec;
26 lines
template <class T, int N> struct Matrix {
typedef Matrix M;
array<array<T, N>, N> d{};
M operator
*
(const M& m) const {
M a;
rep(i,0,N) rep(j,0,N)
rep(k,0,N) a.d[i][j] += d[i][k]
*
m.d[k][j];
return a;
}
vector<T> operator
*
(const vector<T>& vec) const {
vector<T> ret(N);
rep(i,0,N) rep(j,0,N) ret[i] += d[i][j]
*
vec[j];
return ret;
}
M operatorˆ(ll p) const {
assert(p >= 0);
M a, b(
*
this);
rep(i,0,N) a.d[i][i] = 1;
while (p) {
if (p&1) a = a
*
b;
b = b
*
b;
p >>= 1;
}
return a;
}
};
LineContainer.h
Description: Container where you can add lines of the form kx+m, and
query maximum values at points x. Useful for dynamic programming.
Time: O (log N)
32 lines
bool Q;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const {
return Q ? p < o.p : k < o.k;
}
};
struct LineContainer : multiset<Line> {
// (for doubles , use inf = 1/.0 , div (a, b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ˆ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
Q = 1; auto l =
*
lower_bound({0,0,x}); Q = 0;
return l.k
*
x + l.m;
}
};
Treap.h
Description: A short self-balancing tree. It acts as a sequential container
with log-time splits/joins, and is easy to augment with additional data.
Time: O (log N)
55 lines
struct Node {
Node
*
l = 0,
*
r = 0;
int val, y, c = 1;
Node(int val) : val(val), y(rand()) {}
void recalc();
};
int cnt(Node
*
n) { return n ? n->c : 0; }
void Node::recalc() { c = cnt(l) + cnt(r) + 1; }
template<class F> void each(Node
*
n, F f) {
if (n) { each(n->l, f); f(n->val); each(n->r, f); }
}
pair<Node
*
, Node
*
> split(Node
*
n, int k) {
if (!n) return {};
if (cnt(n->l) >= k) { // ”n−>val >= v” for lower bound(v)
auto pa = split(n->l, k);
n->l = pa.second;
n->recalc();
return {pa.first, n};
} else {
auto pa = split(n->r, k - cnt(n->l) - 1);
n->r = pa.first;
n->recalc();
return {n, pa.second};
}
}
Node
*
merge(Node
*
l, Node
*
r) {
if (!l) return r;
if (!r) return l;
if (l->y > r->y) {
l->r = merge(l->r, r);
l->recalc();
return l;
} else {
r->l = merge(l, r->l);
r->recalc();
return r;
}
}
Node
*
ins(Node
*
t, Node
*
n, int pos) {
auto pa = split(t, pos);
return merge(merge(pa.first, n), pa.second);
}
// Example application : move the range [ l , r) to index k
void move(Node
*
& t, int l, int r, int k) {
Node
*
a,
*
b,
*
c;
tie(a,b) = split(t, l); tie(b,c) = split(b, r - l);
if (k <= l) t = merge(ins(a, b, k), c);
else t = merge(a, ins(c, b, k - r));
}
FenwickTree.h
Description: Computes partial sums a[0] + a[1] + ... + a[pos - 1], and
updates single elements a[i], taking the difference between the old and new
value.
Time: Both operations are O (log N).
22 lines
struct FT {
vector<ll> s;
FT(int n) : s(n) {}
void update(int pos, ll dif) { // a[ pos ] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0 , pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
int lower_bound(ll sum) {// min pos s t sum of [0 , pos ] >= sum
// Returns n i f no sum i s >= sum, or −1 i f empty sum is .
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1 << 25; pw; pw >>= 1) {
if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
pos += pw, sum -= s[pos-1];
}
return pos;
}
};
FenwickTree2d.h
Description: Computes sums a[i,j] for all i<I, j<J, and increases single el-
ements a[i,j]. Requires that the elements to be updated are known in advance
(call fakeUpdate() before init()).
Time: O
log
2
N
. (Use persistent segment trees for O (log N).)
"FenwickTree.h" 22 lines
struct FT2 {
vector<vi> ys; vector<FT> ft;
FT2(int limx) : ys(limx) {}
void fakeUpdate(int x, int y) {
for (; x < sz(ys); x |= x + 1) ys[x].push_back(y);
}
void init() {
trav(v, ys) sort(all(v)), ft.emplace_back(sz(v));
}
int ind(int x, int y) {
return (int)(lower_bound(all(ys[x]), y) - ys[x].begin()); }
void update(int x, int y, ll dif) {
for (; x < sz(ys); x |= x + 1)
ft[x].update(ind(x, y), dif);
}
ll query(int x, int y) {
ll sum = 0;
剩余25页未读，继续阅读
iphelf
- 粉丝: 9
- 资源: 9
我的内容管理
展开
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南：步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读：影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程：亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动：计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析：超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪：0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别：技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形：余弦曲线与正弦函数示例
- Matlab 文件操作入门：fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
