一、基本概念

1.线段树是一颗二叉搜索树， 它储存的是区间的信息。

2 每个节点以结构体存储， 结构体包含以下几个信息：

区间左端点， 右端点；

3.线段树的基本思想：二分法

4：1、每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]

 

    2、对于结点k，左孩子结点为2*k，右孩子为2*k+1，这符合完全二叉树的性质

5.线段树可以用来查询区间的最值问题和和问题

 

#include
     
      #include
      
       using namespace std;struct Node {    int l, r, w;//分别表示区间左右端点，w表示区间和} tree[4*1000+1];int x, y, ans;void build(int k, int l, int r) {
   //建立树有值输入    tree[k].l = l;    tree[k].r = r;    if (tree[k].l == tree[k].r) {        scanf("%d", &tree[k].w);        return ;    }    int mid = (l + r) / 2;    build(k*2, l, mid);    build (k*2+1, mid+1, r);    tree[k].w = tree[k*2].w + tree[k*2+1].w;//求区间的和}/*void build(int k, int l, int r) {//建立树无值输入    tree[k].l = l;    tree[k].r = r;  tree[k].w = 0;  if (l < r) {      int mid = (tree[k].l + tree[k].r) >> 1;      build(k<<1, l, mid);      build (k<<1|1, mid+1, r);  }}*/void update(int k) {
   //单点更新    if (tree[k].l == tree[k].r) {        tree[k].w += y;        return ;    }    int mid = (tree[k].l + tree[k].r)/2;    if (x <= mid) update(k*2);    else update(k*2+1);    tree[k].w = tree[k*2].w + tree[k*2+1].w;//求区间的和}void updata1(int k, int x, int y, int w) {
   //区间更新    if (tree[k].l >= x && tree[k].r <= y) {        tree[k].w += w;        return ;    }    int mid = (tree[k].l + tree[k].r) >> 1;    if (y <= mid) updata1(k<<1, x, y, w);    else if (x > mid) updata1(k<<1|1, x, y, w);    else {        updata1(k<<1, x, mid, w);        updata1(k<<1|1, mid+1, y, w);    }}void query(int k) {
   //区间查询    if (tree[k].l >= x && tree[k].r <= y) {        ans += tree[k].w;        return ;    }    int mid = (tree[k].l + tree[k].r) / 2;    if (x <= mid) query(k*2);    if (y > mid) query(k*2+1);}int ask(int k, int x) {
   //单点查询    if (tree[k].l == tree[k].r) {        return tree[k].w;    } else {        int ans = tree[k].w;        int mid = (tree[k].l + tree[k].r) >> 1;        if (x <= mid) ans+=ask(k<<1, x);        else ans+=ask(k<<1|1, x);        return ans;    }}int query1(int k) {
   //最值查询    if (tree[k].l == tree[k].r) {        return tree[k].w;    }    ans = 0;    int mid = (tree[k].l + tree[k].r) / 2;    if (x <= mid) ans = (ans,query(k*2));    else if (y > mid) ans = (ans ,query(k*2+1));    return ans;}int main() {    int t;    scanf("%d", &t);    int count = 1;    while (t--) {        ans = 0;        int n;        scanf("%d", &n);        build(1, 1, n);        printf("Case %d:\n", count++);        string str;        while (cin>>str) {            if (str == "End") break;            scanf("%d%d", &x, &y);            if (str == "Query") {                int ans=query(1);                printf("%d\n", ans);                ans = 0;            } else if (str == "Sub") {                y = -y;                update(1);            } else {                update(1);            }        }    }}