线段树和树状数组的C++代码
线段树#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 = 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, p2 = st;
st = (A <= A) ? 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; // 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 <= A) ? 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;
// if the current interval is included in the update range,
// update that st
if (L == i && R == j) {
A = new_value; // update the underlying array
return st = 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 = (A <= A) ? 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;
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 += v;
}
};
#endif代码源自Steven & Felix, Competitive Programming.
学习。。。。。。。。。。 这个必须要看看那啊
页:
[1]