蒟蒻线段树求调
  • 板块学术版
  • 楼主Rainsleep
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/9/21 21:58
  • 上次更新2023/10/27 10:24:02
查看原帖
蒟蒻线段树求调
666796
Rainsleep楼主2022/9/21 21:58

第一次码qwq,就是单点修改 + 区间查询 \sum

Problem: Code:

#include<bits/stdc++.h>
 
#define int long long 
  
using namespace std;
  
const int N = 500010;
  
struct node
{
    int l,r;
    int sum;
}tr[N << 2];
  
int n,m;
  
inline void build(int idx,int l,int r)
{
    tr[idx] = {l,r,0};
      
    if(l == r)
        return ;
          
    int mid = l + (r - l >> 1);
      
    build(idx << 1,l,mid);
    build(idx << 1 | 1,mid + 1, r);
      
    return ; 
}
  
/*
  
inline void pushup(int idx)
{
    tr[idx].num = tr[idx << 1].sum + tr[idx << 1 | 1];
    return ; 
}
  
*/
  
inline void update(int idx,int pos,int x)//当前节点编号,需要修改元素的位置,需要修改元素的值 
{
    int l = tr[idx].l,r = tr[idx].r;
    tr[idx].sum += x;
      
    if(tr[idx].l == tr[idx].r)// 叶子节点,可以返回了 
        return ;
      
    else
    {
        int mid = l + (r - l >> 1);
          
        if(pos <= mid)
            update(idx << 1,pos,x);
        if(pos > mid)
            update(idx << 1 | 1,pos,x);
                      
        //pushup(idx); 
    }
      
    return ;
}
  
inline int query(int Ql,int Qr,int idx) //当前查询区间的左右端点,当前访问区间的编号 
{
    int l = tr[idx].l;
    int r = tr[idx].r;
      
    if(Ql <= l and Qr >= r)
        return tr[idx].sum;
          
    int mid = l + (r - l >> 1),res = 0;
      
    if(Ql <= mid)
        res += query(Ql,Qr,idx << 1);
    if(Qr > mid)
        res += query(Ql,Qr,idx << 1 | 1);
          
    return res; 
}
  
signed main()
{
      
    scanf("%d %d",&n,&m);
      
    build(1,1,n);
      
    while(m -- )
    {
        int op,l,r;
          
        scanf("%d %d %d",&op,&l,&r);
          
        if(op)
        {
            printf("%d",query(l,r,1));
            putchar('\n');
        }
        else
            update(1,l,r);
          
    }
      
    return 0;
}

一直是91pts,真找不出错哪了qwq,谢谢各位dalao qwq

评测records:

2022/9/21 21:58
加载中...