线段树和树状数组的C++代码

andalousie · 发表于 2014-4-15 09:48:49

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

线段树

#ifndef SEGMENT_TREE
#define SEGMENT_TREE
#include <vector>
class SegmentTree // the segment tree is stored like a heap array
{
std::vector<int> st, A;
int n;
int left (int p) { return p << 1; } // same as binary heap operations
int right(int p) { return (p << 1) + 1; }
void build(int p, int L, int R) // O(n log n)
{
if (L == R) // as L == R, either one is fine
st[p] = L; // store the index
else { // recursively compute the values
build(left(p) , L , (L + R) / 2);
build(right(p), (L + R) / 2 + 1, R );
int p1 = st[left(p)], p2 = st[right(p)];
st[p] = (A[p1] <= A[p2]) ? p1 : p2;
}
}
int rmq(int p, int L, int R, int i, int j) // O(log n)
{
if (i > R || j < L) return -1; // current segment outside query range
if (L >= i && R <= j) return st[p]; // inside query range
// compute the min position in the left and right part of the interval
int p1 = rmq(left(p) , L , (L+R) / 2, i, j);
int p2 = rmq(right(p), (L+R) / 2 + 1, R , i, j);
if (p1 == -1) return p2; // if we try to access segment outside query
if (p2 == -1) return p1; // same as above
return (A[p1] <= A[p2]) ? p1 : p2; // as as in build routine
}
int update_point(int p, int L, int R, int idx, int new_value)
{
// this update code is still preliminary, i == j
// must be able to update range in the future!
int i = idx, j = idx;
// if the current interval does not intersect
// the update interval, return this st node value!
if (i > R || j < L)
return st[p];
// if the current interval is included in the update range,
// update that st[node]
if (L == i && R == j) {
A[i] = new_value; // update the underlying array
return st[p] = L; // this index
}
// compute the minimum pition in the left and right part of the interval
int p1, p2;
p1 = update_point(left(p) , L , (L + R) / 2, idx, new_value);
p2 = update_point(right(p), (L + R) / 2 + 1, R , idx, new_value);
// return the pition where the overall minimum is
return st[p] = (A[p1] <= A[p2]) ? p1 : p2;
}
public:
SegmentTree(const std::vector<int> &_A)
: A(_A), n(static_cast<int>(A.size())) // copy content for local usage
{
st.assign(4 * n, 0); // create large enough vector of zeroes
build(1, 0, n - 1); // recursive build
}
int rmq(const int& i, const int& j) // overloading
{
return rmq(1, 0, n - 1, i, j);
}
int update_point(const int& idx, const int& new_value)
{
return update_point(1, 0, n - 1, idx, new_value);
}
};
#endif

复制代码

树状数组

#ifndef FENWICK_TREE
#define FENWICK_TREE
#include <vector>
class FenwickTree
{
std::vector<int> ft;
int LSOne(int i) { return i & (-i); }
public:
FenwickTree(int n)
{
ft.assign(n+1, 0);
}
int rsq(int b)
{
int sum = 0;
for(; b; b -= LSOne(b))
sum += ft[b];
return sum;
}
int rsq(const int& a, const int& b)
{
return rsq(b) - (a == 1 ? 0 : rsq(a-1));
}
// adjusts value of the k-th element by v (v can be +ve/inc or -ve/dec)
void adjust(int k, int v) // note: n = ft.size() - 1
{
for (; k < static_cast<int>(ft.size()); k += LSOne(k))
ft[k] += v;
}
};
#endif

复制代码

代码源自Steven & Felix, Competitive Programming.

最好是明天 · 发表于 2014-4-15 12:03:55

学习。。。。。。。。。。

simple123 · 发表于 2014-4-18 19:20:09

这个必须要看看那啊

账号		自动登录	找回密码
密码			立即注册

[技术交流] 线段树和树状数组的C++代码

马上注册，结交更多好友，享用更多功能^_^