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

andalousie

线段树

#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.

最好是明天

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

simple123

这个必须要看看那啊